DNA 부분 수열

상근이는 DNA 서열을 연구하는 컴퓨터 과학자로, 두 문자열의 제약이 있는 최대 공통 부분 수열을 구하려고 한다.

알파벳 집합 $\Sigma$의 문자로 이루어진 단어 $w = a_1 a_2 \cdots a_r$ ($a_i \in \Sigma$)를 생각하자. $1 \le i_1 < i_2 < \cdots < i_s \le r$을 만족하는 인덱스로 뽑은 $x = a_{i_1} a_{i_2} \cdots a_{i_s}$를 $w$의 부분 수열이라고 한다. 특히 모든 $j = 1, 2, \ldots, s-1$에 대해 $i_{j+1} = i_j + 1$을 만족하는 부분 수열(즉 연속한 위치의 문자들)을 $w$의 세그먼트라고 한다. 예를 들어 ove는 lovely의 세그먼트이지만, loly는 lovely의 부분 수열일 뿐 세그먼트는 아니다.

두 단어 $w_1$과 $w_2$의 부분 수열이 동시에 되는 단어를 공통 부분 수열이라고 하고, 그중 길이가 가장 긴 것을 최대 공통 부분 수열이라고 한다. 길이가 $0$인 빈 단어는 항상 공통 부분 수열이다.

이제 다음 제약을 추가한다. 선택한 공통 부분 수열은 두 단어 모두에서 연속으로 나타나는 공통 세그먼트들을 순서대로 이어 붙인 형태여야 하며, 사용한 각 공통 세그먼트의 길이는 모두 $K$ 이상이어야 한다. 다시 말해, 공통 부분 수열을 두 단어에 각각 정렬했을 때 서로 맞물려 연속으로 대응되는 문자 덩어리(런) 각각의 길이가 항상 $K$ 이상이어야 한다.

예를 들어 $K = 3$이고 두 단어가 lovxxelyxxxxx, xxxxxxxlovely일 때, lovely는 lov(길이 $3$)와 ely(길이 $3$) 두 공통 세그먼트로 나눌 수 있으므로 조건을 만족한다. 반면 xxxxxxx는 길이가 $K = 3$ 이상인 공통 세그먼트들로만 나눌 수 없으므로 조건을 만족하지 않는다.

두 단어와 $K$가 주어졌을 때, 위 조건을 만족하는 공통 부분 수열의 최대 길이를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 정수 $K$가 주어진다 ($1 \le K \le 100$). 다음 두 줄에는 알파벳 소문자로만 이루어진 두 문자열이 한 줄에 하나씩 주어진다. 각 문자열의 길이는 $1$ 이상 $1000$ 이하이다. 입력의 마지막 줄에는 $0$이 하나 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다, 조건을 만족하는 최대 공통 부분 수열의 길이를 한 줄에 하나씩 출력한다. 조건을 만족하는 길이가 $0$보다 큰 공통 부분 수열이 없으면 $0$을 출력한다.