Beautiful Gift

This Saturday, Windarik is going to meet a girl that he has known from a new MMORPG that he has been playing lately. Windarik is very happy and plan to bring a gift when he meet her from the first time in the real life. In order to impress her, Windarik thought of crafting a hand-made necklace as a present. After spending a whole afternoon, Windarik managed to finish a beautiful necklace. This necklace consists of many beads and each bead has an alphabet printed on it. Before putting the necklace in a box full of love pattern, Windarik made a thorough examination on its quality. While examining the necklace, Windarik asked a question to himself:

"If I remove K type of beads from this necklace, what would the longest remaining chain be?" Two beads are stated to be a different type if and only if the alphabet embedded on those beads are not the same.

Windarik did not decide which type of bead he wanted to remove, instead, he wants to remove the beads such that the longest remaining chain is as long as possible.

For example, let the necklace beads be: "AABACBBACBCA" as shown in Figure 1 (a) below. Note that the necklace is circular, so the end is connected to the beginning of the given string. If Windarik decides to remove (K =) 1 type of beads, since the necklace consists of 3 types of bead (A, B and C), then there are 3 possible combinations:

• Remove all beads of type A, the longest remaining chain would be "CBB" or "CBC" which have the length of 3. See Figure 1 (b).
• Remove all beads of type B, the longest remaining chain would be "CAAA" which has the length of 4. See Figure 1 (c).
• Remove all beads of type C, the longest remaining chain would be "AAABA" which has the length of 5. See Figure 1 (d).

Figure 1

Given a string S which corresponds to the beads arrangement of the necklace and an integer K, determine the longest remaining chain after we remove K type of beads from the necklace.

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with an integer K and a string S (0 ≤ K ≤ π(S); 1 ≤ |S| ≤ 20,000; S_i ∈ {A-Z} ∀i=1..|S|) where π(S) is the number of distinct character in S.

Output

For each case, output in a line the "Case #X: Y" where X is the case number starts from 1, and Y is the length of the longest remaining chain after we remove K type of beads.

4
1 AABACBBACBCA
2 AABACBBACBCA
3 AABACBBACBCA
5 INDONESIANATIONALCONTEST

Case #1: 5
Case #2: 3
Case #3: 0
Case #4: 9

Explanation for the 2^nd sample input.

Remove all beads of type B and C, and we get the longest possible remaining chain "AAA" of length 3.

Explanation for the 3^rd sample input.

K is equal to π(S), so the necklace is completely gone.