M. Until next time, SCNUCPC!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After SCNUCPC ends, Yachiyo wants to restore Magic Street to its usual look.

There are $$$n$$$ stalls in a row on Magic Street. Each stall has only two states: already arranged as type C, or not arranged yet, marked as ?. The initial state of the stalls is represented by a string of length $$$n$$$, containing only C and ?. It is guaranteed that the first stall and the last stall are both type C stalls. Yachiyo needs to turn some ? into C, while the remaining positions stay as ?.

Let the positions of the type C stalls on the street, in order, be $$$p_1,p_2,\dots,p_k$$$. For any $$$i \gt 1$$$, the type C stall at position $$$p_i$$$ causes an opening cost of $$$p_i \cdot (p_i-p_{i-1})$$$.

Your task is to find the minimum total opening cost when there are exactly $$$k$$$ type C stalls on Magic Street.

Input

Each test file contains multiple test cases. The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10^3)$$$, the number of test cases.

For each test case, the first line contains two integers $$$n,k$$$ $$$(2 \leq k \leq n \leq 2 \times 10^5)$$$, denoting the total number of stalls and the number of type C stalls.

The next line contains a string of length $$$n$$$, containing only C and ?, representing the initial state of the stalls on Magic Street. It is guaranteed that the number of C stalls does not exceed $$$k$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output one line containing one integer, the minimum total opening cost.

Example
Input
2
5 2
C???C
7 4
CC????C
Output
20
31
Note

In the first test case of the sample, C???C is the only plan, and the opening cost is $$$5 \times (5 - 1) = 20$$$.

In the second test case of the sample, the plan CC?C??C minimizes the cost, and the opening cost is $$$2 + 8 + 21 = 31$$$.