In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
A word is called a period of the word if it is not longer than and there exists a natural number such that is a prefix of . E.g., the periods of the word entente are: ent, entent and entente.
The teacher wrote a very long word on the whiteboard. Bytie was not really interested in what was the class about but he wrote down in his notebook all the words that can be obtained from the word on the whiteboard by removing exactly one letter. Now he would like to choose the word in his list with the shortest shortest period. Write a program that will help him with this problem.
The first line of the standard input contains one integer (), the number of test cases. lines follow, each of them contains one integer () that denotes the length of the word on the whiteboard and a -letter word composed of small English letters.
Your program should write lines to the standard output. The -th line should contain the answer for the -th test case: one integer equal to the length of the shortest period among all the shortest periods of the words written in Bytie's notebook.
For the input data:
1 8 ababcaba
the correct result is:
2
Explanation of the example: Here are the words written by Bytie, together with the length of their shortest periods:
Task author: Jacek Tomasiewicz.