Inexact string

We say that the lines a and b are k differences, if the lengths of these lines are identical, and the characters in positions with the same numbers same everything, except the k pieces. For example, line ABABAC and BBABAB have 2 differences.

In this line S of length N symbols and the number of k is required to find two strings of equal length, starting from different positions, and having no more than k differences. The line consists of uppercase Latin characters.

Input

The input file contains the first line an integer k, in the second - the string S.

Output

The output file should contain an integer number - the length of the longest matched string, or 0 (zero) if no solution exists.

0 ≤ k ≤ N ≤ 1000

Examples