ove lovely loly lovely Thomas, a computer scientist that works with DNA sequences, needs to compute longest common subsequences of given pairs of strings. Consider an alphabet \textbf{Σ} of letters and a word \textit{\textbf{w}}\textbf{=}\textit{\textbf{a}}\textbf{_1}\textit{\textbf{a}}\textbf{_2 …}\textit{\textbf{a}}\textbf{_r}, where \textit{\textbf{a}}\textbf{_i} ∈ \textbf{Σ}, for \textit{\textbf{i}} = \textbf{1}, \textbf{2}, …,\textit{ }\textit{\textbf{r}}. A \textit{subsequence} of \textit{\textbf{w}} is a word \textit{\textbf{x}}\textbf{=}\textit{\textbf{a}}\textbf{_i1}\textit{\textbf{a}}\textbf{_i2 …}\textit{\textbf{a}}\textbf{_is} such that \textbf{1} ≤ \textit{\textbf{i}}\textbf{_1} < \textit{\textbf{i}}\textbf{_2} < … < \textit{\textbf{i}}\textbf{_s} ≤ \textit{\textbf{r}}. Subsequence \textit{\textbf{x}} is a \textit{segment} of \textit{\textbf{w}} if \textit{\textbf{i}}\textbf{_\{j+1\}=}\textit{\textbf{i}}\textbf{_j + 1}, for \textit{\textbf{j}} = \textbf{1}, \textbf{2}, …,\textit{ }\textit{\textbf{s}}\textbf{-1}. For example the word is a segment of the word , whereas the word is a subsequence of , but not a segment. lovxxelyxxxxx xxxxxxxlovely lovely xxxxxxx A word is a \textit{common subsequence} of two words \textit{\textbf{w}}\textbf{_1} and \textit{\textbf{w}}\textbf{_2} if it is a subsequence of each of the two words. A \textit{longest common subsequence} of \textit{\textbf{w}}\textbf{_1} and \textit{\textbf{w}}\textbf{_2} is a common subsequence of \textit{\textbf{w}}\textbf{_1} and \textit{\textbf{w}}\textbf{_2} having the largest possible length. For example, consider the words \textit{\textbf{w}}\textbf{_1=} and \textit{\textbf{w}}\textbf{_2=}. The words \textit{\textbf{w}}\textbf{_3=} and \textit{\textbf{w}}\textbf{_4=}, the latter of length \textbf{7}, are both common subsequences of \textit{\textbf{w}}\textbf{_1} and \textit{\textbf{w}}\textbf{_2}. In fact, \textit{\textbf{w}}\textbf{_4} is their longest common subsequence. Notice that the empty word, of length zero, is always a common subsequence, although not necessarily the longest. lovely lovxxelyxxxxx xxxxxxxlovely xxxxxxx In the case of Thomas, there is an extra requirement: the subsequence must be formed from common segments having length \textit{\textbf{K}} or more. For example, if Thomas decides that \textit{\textbf{K}}\textbf{=3}, then he considers to be an acceptable common subsequence of and , whereas , which has length \textbf{7} and is also a common subsequence, is not acceptable. Can you help Thomas? \InputFile The input contains several test cases. The first line of a test case contains an integer \textit{K} representing the minimum length of common segments, where \textbf{1} ≤ \textit{\textbf{K}} ≤ \textbf{100}. The next two lines contain each a string on lowercase letters from the regular alphabet of \textbf{26} letters. The length \textit{\textbf{l}} of each string satisfies the inequality \textbf{1} ≤ \textit{\textbf{l}} ≤ \textbf{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. \OutputFile 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 \textit{\textbf{K}} from both strings. If no such common subsequence of length greater than zero exists, then \textbf{0} must be printed.