Kruskal-chan is troubled by a strange string puzzle today!

A junior standing nearby tilts their head: "Isn't this the kind of problem you are best at, senior?"

Kruskal-chan's face turns slightly red: "Hmph, hmph! Of course, it can't stump me!"

A run of a string is defined as a non-empty substring that contains only one type of character and cannot be extended. For example, aabaa has three runs: aa, b, and aa.

Given a string of length $n$, you can cut it into three non-empty strings and reassemble them in any order to form a new string. Calculate how many different schemes result in the new string having exactly $k$ runs.

Note: Two schemes are considered different if and only if the cut positions are different or the reassembly order is different. There are 6 possible reassembly orders.

Input

The problem contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^5$), representing the number of test cases.

For each test case, the first line contains two integers, representing the string length $n$ ($3 \le n \le 10^5$) and the number of runs $k$ ($1 \le k \le n$).

The next line contains a string of length $n$, consisting only of lowercase English letters.

It is guaranteed that $\sum n \le 10^5$.

Output

Output $T$ lines, each containing an integer representing the number of schemes.

Examples

Input 1

2
8 5
abbccaba
3 1
abc

Output 1

45
0

Note

In the first example, cutting the string into three segments abb, cc, and aba, and placing the third segment at the very beginning, results in abaabbcc, which has 5 runs and satisfies the requirement.