Broken Keyboard

Interview

Time limit1sMemory limit128 MB

Summary

For each test case, find the length of the longest substring of the sentence that contains at most m distinct characters.

Level: Medium5 of 10
Topics: Sliding window, String, Hash map, Two pointers
Solved: No attempts yet

Problem

A keyboard is broken, and only some of its keys still work. Exactly $m$ keys work, and the keyboard layout (the mapping from keys to characters) cannot be changed. Each key maps to exactly one character, and a character cannot be produced by combining several keys.

Given a sentence you want to type, find the length of the longest contiguous substring that can be typed without changing the layout. Because $m$ keys work, this is the same as finding the length of the longest contiguous substring that contains at most $m$ distinct characters.

Input

The input consists of several test cases. Each test case spans two lines.

The first line contains the number of working keys $m$ ( $1 \le m \le 128$ ).
The second line contains the sentence to type. Its length does not exceed 1,000,000 characters, and it may contain spaces. A space counts as a character.

The last line of the input contains a single $0$ , which marks the end of the input.

Output

For each test case, print on its own line the length of the longest contiguous substring that consists of at most $m$ distinct characters.

Examples3

Example 1

Input

5
This can't be solved by brute force.
1
Mississippi
0

Expected output

7
2

Example 2
Input
```
1
aaaa
0
```
Expected output
```
4
```
Example 3
Input
```
1
abcdef
0
```
Expected output
```
1
```