DNA 부분 수열

상근이는 DNA 수열을 연구하는 컴퓨터 과학자이다. 오늘은 두 문자열의 최대 공통 부분 수열을 구해보려고 한다.

알파벳 Σ으로 이루어진 단어 w = a1a2...ar (ai ∈ Σ for i = 1,2,...r)이 있다. w의 부분 수열은 1 ≤ i1 < i2 < .... < is ≤ r을 만족하는 x=ai1ai2...ais 이다. 모든 j = 1,2,...,s-1에 대해서 ij+1 = ij + 1을 만족하는 부분 수열 x를 w의 세그먼트라고 한다. 예를 들어, lovely는 ove의 세그먼트이다. 하지만, loly는 lovely의 부분 수열이지만, 세그먼트는 아니다.

두 단어 w1과 w2의 부분 수열이 되는 단어를 공통 부분 수열이라고 한다. 최대 공통 부분 수열은 w1와 w2의 공통 수열 중에서 길이가 가장 긴 것을 말한다. 예를 들어, w1 = lovxxelyxxxxx, w2 = xxxxxxxlovely인 경우에 w3 = lovely와 w4 = xxxxxxx는 w1와 w2의 공통 부분 수열이다. w4는 길이가 7이며, 두 단어 w1과 w2의 최대 공통 부분 수열이 된다. 길이가 0인 빈 단어는 항상 공통 부분 수열이다.

상근이는 부분 수열이 반드시 길이가 K이상인 공통 세그먼트를 포함해야 한다는 조건을 추가했다. 예를 들어, K=3인 경우에 lovxxelyxxxxx와 xxxxxxxlovely의 공통 부분 수열로 lovely는 가능하지만, xxxxxxx는 가능하지 않다. xxxxxxx에는 길이가 3 이상인 공통 세그먼트가 포함되어 있지 않기 때문이다.

두 단어가 주어졌을 때, 길이가 K 이상인 공통 세그먼트를 포함하는 최대 공통 부분 수열의 길이를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 K가 주어진다. (1 ≤ K ≤ 100) 다음 두 줄에는 알파벳 소문자로만 이루어진 두 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같으며, 103을 넘지 않는다.

입력의 마지막 줄에는 0이 하나 주어진다.

각 테스트 케이스마다 길이가 K 이상인 공통 세그먼트를 포함한 최대 공통 부분 수열의 길이를 출력한다. 만약, 0보다 큰 공통 수열이 없는 경우에는 0을 출력한다.