E. Nearly Shortest Repeating Substringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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 = \underbrace{k + \cdots + k}_{x\rm\ \text{times}} for some positive integer x, strings s and c has the same length and c_i \neq s_i for at most one i (i.e. there exist 0 or 1 such positions).InputThe first line contains a single integer t (1 \leq t \leq 10^3) — the number of test cases.The first line of each test case contains a single integer n (1 \leq n \leq 2\cdot10^5) — 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\cdot10^5.OutputFor each test case, print the length of the shortest string k satisfying the constraints in the statement.ExampleInput
54abaa4abba13slavicgslavic8hshahaha20stormflamestornflameOutput
1
4
13
2
10
NoteIn the first test case, you can select k = \texttt{a} and k+k+k+k = \texttt{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 = \texttt{abba}, which is equal to s.
54abaa4abba13slavicgslavic8hshahaha20stormflamestornflame
1 4 13 2 10 
['brute force', 'implementation', 'number theory', 'strings', '*1500']