사악한 바스커 가문의 신

그다지 유명하지 않은 작가 아서 코난 모일(Arthur Conan Moyle)은 자신의 책이 마땅히 받아야 한다고 믿는 만큼 인기를 끌지 못하는 이유를 마침내 알아냈습니다. 같거나 매우 비슷한 구절이 자꾸 반복되어 글이 지루해진다는 것이었습니다. 그는 책을 개선하는 가장 좋은 방법이 처음 반복이 나타나는 지점부터 뒤의 내용을 전부 버리는 것이라고 결론지었습니다. 그러면 책이 열린 결말 같은 흥미로운 느낌을 갖게 됩니다.

처음에는 완전히 똑같은 구절을 찾으려 했지만 실패했습니다. 반복되는 구절이 정확히 일치하는 경우는 드물기 때문입니다. 처음에는 소문자였던 글자가 두 번째에는 대문자가 되기도 하고 그 반대도 있으며, 문장 부호가 조금 다르거나 문장 속 단어의 순서가 살짝 바뀌기도 합니다. 이를 해결하기 위해 그는 중복을 인식하는 아래의 더 너그러운 기준을 고안했습니다. 이 기준에는 양의 정수 매개변수 $k$가 있으며, $k$를 바꾸면 얼마나 긴 반복 구절까지 중복으로 볼지 조절할 수 있습니다.

알파벳 문자는 a–z와 A–Z 글자입니다. 대소문자는 구분하지 않으므로 a와 A는 같은 글자로 봅니다.

두 문자열 $S_1$과 $S_2$가 글자의 순열을 무시하고 $k$-동일하다는 것은 다음을 모두 만족한다는 뜻입니다.

• $S_1$과 $S_2$는 모두 알파벳 문자로 시작하고 알파벳 문자로 끝난다.
• $S_1$과 $S_2$는 모두 정확히 $k$개의 알파벳 문자를 포함한다.
• 모든 알파벳 문자 $c$에 대해, $S_1$에 들어 있는 $c$의 개수와 $S_2$에 들어 있는 $c$의 개수가 같다.

바꿔 말하면, $S_1$과 $S_2$가 글자의 순열을 무시하고 $k$-동일하다면 두 문자열이 사용하는 알파벳 문자는 (중복 개수까지 포함해) 완전히 같고, 다만 나열 순서만 다를 수 있습니다.

작가의 책이 하나 주어질 때, 글자의 순열을 무시하고 $k$-동일한 두 부분 문자열을 포함하지 않는 가장 긴 앞부분을 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 두 줄로 주어집니다.

첫째 줄에는 정수 $k$가 주어지며 $1 \le k \le 50$입니다.

둘째 줄에는 문자열 $T$가 주어집니다. $T$의 길이는 최대 $100,000$자입니다. $T$에는 공백을 포함한 알파벳이 아닌 문자가 들어갈 수 있지만, 특별한 의미를 갖는 문자(즉 ASCII 코드가 $32$보다 작은 문자)는 들어 있지 않습니다.

입력의 끝은 $0$ 하나만 있는 줄로 표시됩니다.

각 테스트 케이스마다 한 줄을 출력합니다. $i$번째 테스트 케이스에 대해서는 정수 하나를 출력하는데, 그 값은 해당 테스트 케이스의 문자열 $T$의 접두사 $P$ 중에서, 글자의 순열을 무시하고 $k$-동일한 서로 다른(단, 겹치지 않을 필요는 없는) 두 부분 문자열 $S_1$과 $S_2$를 포함하지 않는 가장 긴 접두사 $P$의 길이(알파벳이 아닌 문자까지 모두 포함)입니다.