Captain Amol Kalia is a detective. Digo is a Microsoft engineer. Madam Mischievous is very mischievous. Amolia Kali is Captain Amol Kalia's girlfriend.
Since Digo's income is quite greater than Amol Kalia's income, Amolia Kali decided to switch the boyfriends.

For this task, she gave Digo an array of differently colored chocolates and asked to give her a maximum spread of same colored chocolates by applying at max "maxSwap" swaps. A swap can occur only between two consecutive chocolates. A spread is defined as maximum range of consecutively occurring same colored chocolates.
For example, chocolate array is {red,red,red,blue,red,blue,blue,black}, then spread of red is 3, blue is 2 and black 1. So, overall spread of array is 3.

So, help Digo to find out the maximum spread he can attain. (To be continued..)

**Constraints**

- "chocolatecolours" will contain between 1 and 50 characters, inclusive.

- Each character in chocolatecolors will be an uppercase letter ('A'-'Z').

- maxSwaps will be between 1 and 2500, inclusive.

- Number of test cases<=100

- Time limit: 5 sec.

**Input:**

First line contains t, no. of test cases.

T lines follow containing a string and a number separated by space, representing Chocolatecolors and maxswaps respectively.

**Output:**

T lines containing the answer to each test case.

**Examples**

5

ABCDCBC 1

ABCDCBC 2

ABBABABBA 3

ABBABABBA 4

QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSJYIWFOO 77

**Output:**

2

3

4

5

5

**Explanation:**

1. One optimal solution is to swap chocolates at positions 2 and 3, obtaining the row "ABDCCBC", which has spread 2.

2. The only optimal solution is to produce the row "ABDCCCB".

3. The row "ABBBBAABA" can be produced with 3 swaps.

4. An optimal solution is to produce the row "AABBBBBAA".