Word cutting

On a cyclic tape, small Latin letters are inscribed. For a role-playing game, you need to extract at least k identical words. The longer the word, the more engaging the game becomes. Determine the length of the longest word that can be extracted at least k times.

Input

The input consists of multiple test cases. Each line represents a single test case, containing the integer k and a non-empty string of letters on the tape. The input concludes at the end of the file. Across all test cases, the total number of letters on all tapes combined does not exceed 10^5. All numbers in the input are positive integers and do not exceed 10^5.

Output

For each test case, output the length of the longest word that can be extracted at least k times.

Examples