Description

It is a beautiful afternoon. Little W and Little C are practicing the skill of bundling bamboo poles in a bamboo grove.

There are infinitely many identical short bamboos in the grove. Each short bamboo consists of $n$ segments.

These bamboos are special: every segment is dyed a color. There are 26 possible colors, represented by lowercase letters $\underline{a}$ to $\underline{z}$. In other words, if you write down the colors from the bottom end to the top end of a bamboo, you get a string of lowercase letters.

Little W and Little C are masters at bundling bamboos. They know how to bind scattered short bamboos into one long bamboo pole. Initially, you hold one short bamboo as the current pole. Each time, you may choose one short bamboo and bind some number of its bottom segments (possibly $0$) one by one to the top segments of the current pole. The remaining segments in front protrude, producing a longer pole. Note that the bottom end is the end near the root; you cannot flip a bamboo.

Little W has high aesthetic standards. He has a habit when bundling: if two segments of two bamboos are bound together, then their colors must be the same.

Suppose a short bamboo’s colors from bottom to top are $\underline{aba}$.

Then two bamboos can be bundled end-to-end to obtain a pole with colors $\underline{abaaba}$; you can also bind the top segment $\underline{a}$ of the first bamboo to the bottom segment $\underline{a}$ of the second bamboo to obtain $\underline{ababa}$; you can also align every segment and bind them all, forming a pole with colors $\underline{aba}$.

If we bundle another short bamboo on top of the pole with colors $\underline{ababa}$, we can obtain three different outcomes: $\underline{ababaaba}$, $\underline{abababa}$, and $\underline{ababa}$.

However, Little C disagrees. He believes Little W cannot produce many different lengths of bamboo poles. Little W is not convinced and asks you for help—please compute, under the constraint that the pole length does not exceed $w$, how many distinct lengths of bamboo poles Little W can produce. Here, the length of a pole is the number of segments from the bottom end to the top end.

Note: If $w < n$, then there is no valid length. In this case, the answer is $0$.

Input Format

The input file is jie.in. The first line contains one integer $T$, the number of test cases.

For each test case, the first line contains two positive integers $n$ and $w$, representing the length of a short bamboo and the upper bound on the pole length.

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

Output Format

The output file is jie.out.

Output $T$ lines. Each line contains one integer, the number of distinct lengths obtainable by bundling.

1
4 11
bbab

5

2
44 1000
baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa
41 1000
abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb

195
24

Hint

[Sample Explanation 1]

There are 6 different configurations of poles with length not exceeding $11$:

bbab
bbabbab
bbabbbab
bbabbabbab
bbabbabbbab
bbabbbabbab

The last two poles have the same length, so there are 5 distinct lengths. The lengths are: $4$, $7$, $8$, $10$, $11$.

Constraints

For all testdata, all strings consist of lowercase letters.

Each test point satisfies the following agreement:

Translated by ChatGPT 5