Codeforces Round 937 (Div. 4) |
---|
Finished |
You are given a string s of length n consisting of lowercase Latin characters. Find the length of the shortest string k such that several (possibly one) copies of k can be concatenated together to form a string with the same length as s and, at most, one different character.
More formally, find the length of the shortest string k such that c=k+⋯+k⏟x times for some positive integer x, strings s and c has the same length and ci≠si for at most one i (i.e. there exist 0 or 1 such positions).
The first line contains a single integer t (1≤t≤103) — the number of test cases.
The first line of each test case contains a single integer n (1≤n≤2⋅105) — the length of string s.
The second line of each test case contains the string s, consisting of lowercase Latin characters.
The sum of n over all test cases does not exceed 2⋅105.
For each test case, print the length of the shortest string k satisfying the constraints in the statement.
54abaa4abba13slavicgslavic8hshahaha20stormflamestornflame
1 4 13 2 10
In the first test case, you can select k=a and k+k+k+k=aaaa, which only differs from s in the second position.
In the second test case, you cannot select k of length one or two. We can have k=abba, which is equal to s.
Name |
---|