It is a beautiful afternoon, and Xiao W and Xiao C are practicing their bamboo-tying skills in the bamboo forest.

There are countless identical short bamboo sticks in the bamboo forest, each consisting of $n$ segments.

These bamboo sticks are special; each segment is dyed with a color. There are 26 possible colors, represented by lowercase English letters 'a' through 'z'. This means that if you write down the colors of the segments from the bottom to the top, they form a string of lowercase English letters.

Xiao W and Xiao C are both experts at tying bamboo sticks, and they know how to tie scattered short bamboo sticks into one long bamboo pole. Initially, you take one short bamboo stick as the current bamboo pole. Each time, you can choose a short bamboo stick and tie some number of segments (possibly 0) from the bottom of the short bamboo stick to the corresponding segments at the top of the bamboo pole, while the remaining segments of the short bamboo stick extend outward, thus obtaining a longer bamboo pole. Note that the bottom of the bamboo stick is the end near the root, and it cannot be inverted.

Xiao W has very high aesthetic standards for bamboo poles, and he has a quirk when tying them: if two segments from two different bamboo sticks are tied together, their colors must be the same.

Suppose a short bamboo stick has colors from bottom to top as aba.

Then, two bamboo sticks can be tied end-to-end to get a bamboo pole with colors abaaba; you can also tie the top segment 'a' of the first stick with the bottom segment 'a' of the second stick to get a bamboo pole with colors ababa; or you can directly align every segment to tie them into a bamboo pole with colors aba.

Suppose we tie another bamboo stick to the top of a bamboo pole with colors ababa, we can get three different cases: ababaaba, abababa, and ababa.

However, Xiao C has a different opinion on this problem; he believes that Xiao W cannot tie many bamboo poles of different lengths. Xiao W is very unconvinced, so he has come to you—now please calculate how many different lengths of bamboo poles Xiao W can tie such that the length does not exceed $w$. Here, the length of a bamboo pole refers to the number of segments from the bottom to the top.

Note: If $w < n$, there are no valid lengths, and the answer is 0.

Input

The first line contains one integer $T$, the number of test cases.

The first line of each test case contains two positive integers $n$ and $w$, representing the length of the short bamboo stick and the upper limit of the bamboo pole length, respectively.

The second line of each test case contains a string of length $n$, consisting only of lowercase English letters, representing the colors of the short bamboo stick from bottom to top.

Output

Output $T$ lines, each containing an integer representing the number of different lengths of bamboo poles that can be tied.

Examples

Input 1

1
4 11
bbab

Output 1

5

Note 1

There are 6 different cases for bamboo poles with length not exceeding 11: bbab bbabbab bbabbbab bbabbabbab bbabbabbbab bbabbbabbab The last two bamboo poles have the same length, so there are 5 different lengths in total. The lengths are: 4, 7, 8, 10, 11.

Input 2

2
44 1000
baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa
41 1000
abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb

Output 2

195
24

Input 3

See jie/jie.in and jie/jie.ans in the contestant directory.

Constraints

For all test cases, it is guaranteed that all strings consist of lowercase English letters. The test cases satisfy the following constraints: