Dazhongfeng has a string of length $n$. He knows that one of its substrings is the password to a treasure passed down by his ancestors. However, because the string is very long, it is difficult for Dazhongfeng to try all these substrings one by one.

One day, Dazhongfeng went to Mr. Jia-Ben to have his fortune told, but Mr. Jia-Ben said, "Heaven's secrets must not be leaked."

After Dazhongfeng's persistent begging, Mr. Jia-Ben told him: "The password is a substring that appears exactly $k$ times in the string."

However, Dazhongfeng did not know what to do. After his repeated pleas, Mr. Jia-Ben, seeing his sincerity, told him: "Among the substrings that appear exactly $k$ times, classify them by their length; the password is in the category with the most substrings."

To find this password, Dazhongfeng wants you to help him find the length that appears most frequently among substrings occurring exactly $k$ times (if there are multiple such lengths, output the largest one).

Input

The first line contains a positive integer $T$, representing the number of test cases. Following this are $T$ lines, each containing a string and a positive integer $k$.

Output

Output $T$ lines in total, each containing an integer representing the length that appears most frequently among substrings occurring exactly $k$ times. If no substring appears exactly $k$ times, output $-1$.

Examples

Input 1

6
aab 1
abc 1
aaaa 2
abab 2
ababacc 2
abab 4

Output 1

2
1
3
4
1
2
-1

Note

For the first case: The substrings $b, aa, ab, aab$ all appear exactly once. Among these, substrings of length 1 appear 1 time, substrings of length 2 appear 2 times, and substrings of length 3 appear 1 time. Thus, the answer is 2.

For the second case: The substrings $a, b, c, ab, bc, abc$ all appear exactly once. Among these, substrings of length 1 appear 3 times, substrings of length 2 appear 2 times, and substrings of length 3 appear 1 time. Thus, the answer is 1.

For the third case: The substring $aaa$ appears twice, which is a substring of length 3. No other lengths occur. Thus, the answer is 3.

For the fourth case: The substrings $a, b, ab$ appear twice. Among these, substrings of length 1 appear 2 times, and substrings of length 2 appear 1 time. Thus, the answer is 1.

For the fifth case: The substrings $b, c, ab, ba$ appear twice. Among these, substrings of length 1 appear 2 times, and substrings of length 2 appear 2 times. Thus, the answer is 2.

For the sixth case: No substring appears four times. Thus, the answer is -1.

Constraints

For 20% of the data: $1 \le k \le n \le 10$ For 100% of the data: $1 \le n \le 10^5, 1 \le T \le 100, \sum n \le 3 \times 10^6$