Söz dövrü

Називək dövrü söz s elə bir söz t ki, uzunluğu söz s-in uzunluğundan artıq deyil və elə bir təbii ədəd k mövcuddur ki, söz s söz t^k-nin prefiksi olur (yəni k nüsxə söz t-nin birləşməsi ilə əldə edilən söz). Məsələn, söz xyzxyzx-in dövrləri xyz, xyzxyz, xyzxyzx sözləridir.

Tutaq ki, uzunluğu l olan bir söz w var. l uzunluğunda olan l - 1 sözləri nəzərdən keçirək, bunlardan i-ci söz w-dən i-ci hərfi çıxarılaraq əldə edilir. Bu sözlərin hər biri üçün ən kiçik uzunluqlu dövrü tapın. Əldə edilən l ədədlərdən ən kiçiyini çıxarın.

Giriş verilənləri

Birinci sətirdə testlərin sayı d (1 ≤ d ≤ 10) verilir. Hər bir test bir sətirdən ibarətdir. i-ci testin əvvəlində n_i (2 ≤ n_i ≤ 200000) - i sözünün uzunluğu l verilir. Sonra boşluqla ayrılmış l kiçik latın hərflərindən ibarət söz w gəlir.

Çıxış verilənləri

Hər bir test üçün ayrı sətirdə bir ədəd çıxarın - başlanğıc sözdən bir hərf çıxarılaraq əldə edilən sözün dövrünün minimal uzunluğu.

Nümunələr

Qeyd

Testdəki söz w üçün aşağıdakı sözlər, ən kiçik dövrlər və onların uzunluqları var:

• babcaba — babca — uzunluğu 5;

• aabcaba — aabcab — uzunluğu 6;

• abbcaba — abbcab — uzunluğu 6;

• abacaba — abac — uzunluğu 4;

• abababa — ab — uzunluğu 2;

• ababcba — ababcb — uzunluğu 6;

• ababcaa — ababca — uzunluğu 6;

• ababcab — ababc — uzunluğu 5.

Buna görə də, uzunluqların ən kiçiyi 2-dir ki, bu da test nümunəsinə cavabdır.