ove
lovely
loly
Thomas, a computer scientist that works with DNA sequences, needs to compute longest common subsequences of given pairs of strings. Consider an alphabet Σ of letters and a word w=a_1a_2 …a_r, where a_i ∈ Σ, for i = 1, 2, …, r. A subsequence of w is a word x=a_i1a_i2 …a_is such that 1 ≤ i_1 < i_2 < … < i_s ≤ r. Subsequence x is a segment of w if i_{j+1}=i_j + 1, for j = 1, 2, …, s-1. For example the word is a segment of the word , whereas the word
The input contains several test cases. The first line of a test case contains an integer K representing the minimum length of common segments, where 1 ≤ K ≤ 100. The next two lines contain each a string on lowercase letters from the regular alphabet of 26 letters. The length l of each string satisfies the inequality 1 ≤ l ≤ 10^3. There are no spaces on any line in the input. The end of the input is indicated by a line containing a zero.
For each test case in the input, your program must print a single line, containing the length of the longest subsequence formed by consecutive segments of length at least K from both strings. If no such common subsequence of length greater than zero exists, then 0 must be printed.