Mr. Shim is a kind and caring teacher. He wants you to feel the love by giving you very difficult math problems! The harder the math problem, the greater amount of love you will feel. Math problems will be represented by a sequence of characters.
The difficulty of the problem is determined by complexity. All of the sequences contain a repeating pattern. The complexity of a sequence is determined by the length of the pattern, divided by the number of times it repeats.
abababab would have a pattern length of ~4~ and it repeats twice. Therefore, the complexity is ~2~. Having
ab ~4~ times yields a significantly simpler problem and less love - so we don't want that! The sequence
ababababababab however, will have length ~2~ and ~7~ repetitions, as if a higher length was used then there would be symbols not included in the pattern. Additionally, the length of the pattern must be less than the length of the sequence, so you can never use just one repetition in your calculations.
You'll be given ~N~ sequences of length ~M~. It is your job to determine the complexity of the problem that will cause you to feel the greatest amount of love!
~1 \leq N \leq 10\,000~
~1 \leq M \leq 22\,500~
The first line will contain ~N~, the number of sequences. A pattern can be formed with all sequences.
The following ~N~ lines will contain an integer, ~M~ (the length of the string) and the string representing the sequence. The string will not contain whitespace characters.
The complexity value of the sequence that will cause you to feel the most love.
Sample Input 1
3 12 'shl,g'shl,g 12 pgpgpgpgpgpg 30 7hl7hl7hl7hl7hl7hl7hl7hl7hl7hl
Sample Output 1
Sample Input 2
5 40 uxquhwbtgauxquhwbtgauxquhwbtgauxquhwbtga 40 i''g-a0jn6i''g-a0jn6i''g-a0jn6i''g-a0jn6 42 5-oq=v=5-oq=v=5-oq=v=5-oq=v=5-oq=v=5-oq=v= 36 vfb9vfb9vfb9vfb9vfb9vfb9vfb9vfb9vfb9 30 ==.=s==.=s==.=s==.=s==.=s==.=s
Sample Output 2