#P1950E. Nearly Shortest Repeating Substring
Nearly Shortest Repeating Substring
Description
You are given a string of length consisting of lowercase Latin characters. Find the length of the shortest string such that several (possibly one) copies of can be concatenated together to form a string with the same length as and, at most, one different character.
More formally, find the length of the shortest string such that for some positive integer , strings and has the same length and for at most one (i.e. there exist or such positions).
The first line contains a single integer () — the number of test cases.
The first line of each test case contains a single integer () — the length of string .
The second line of each test case contains the string , consisting of lowercase Latin characters.
The sum of over all test cases does not exceed .
For each test case, print the length of the shortest string satisfying the constraints in the statement.
Input
The first line contains a single integer () — the number of test cases.
The first line of each test case contains a single integer () — the length of string .
The second line of each test case contains the string , consisting of lowercase Latin characters.
The sum of over all test cases does not exceed .
Output
For each test case, print the length of the shortest string satisfying the constraints in the statement.
Note
In the first test case, you can select and , which only differs from in the second position.
In the second test case, you cannot select of length one or two. We can have , which is equal to .