Little Cyan Fish has a row of $n$ balls. Each ball is either cyan or white. The row is described by a string $s$ of length $n$, where $C$ denotes a cyan ball and $W$ denotes a white ball.

In one operation, he chooses a cyan ball in the current row. Suppose this ball is at position $i$ in the current row. Then all balls whose positions differ from $i$ by at most $k$ are deleted, including the chosen cyan ball itself. After the deletion, the remaining left and right parts are concatenated.

For example, when $k = 1$, one possible operation is

where the ball with the thick border is chosen and the balls inside the red box are deleted.

Find the minimum number of operations needed to delete the whole row. If it is impossible, report that.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T$), indicating the number of test cases.

For each test case, the first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$). The second line contains a string $s$ of length $n$, consisting only of characters $C$ and $W$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, if it is impossible to delete the whole row, output a single line with a single integer $-1$. Otherwise, output a single line containing a single integer, indicating the minimum number of operations needed to delete the whole row.

Examples

Input 1

3
1 1
C
5 2
WWCWW
4 1
WWWW

Output 1

1
1
-1

Note

In the first sample test case, Little Cyan Fish chooses the only ball.

In the second sample test case, he chooses the middle cyan ball; because $k = 2$, the whole row is deleted in one operation.

In the third sample test case, there is no cyan ball, so no operation can be performed.