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.

For example 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!

Constraints

~1 \le N \le 10\,000~

~1 \le M \le 22\,500~

Input Specification

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.

Output Specification

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

7.50

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

10.50