You are given a strip of paper that is cells long. Each cell is either black or white. In an operation you can take any consecutive cells and make them all white.
Find the minimum number of operations needed to remove all black cells.
Input The first line contains a single integer (1 \leq t \leq 1000$$1 \leq t \leq 1000) — the number of test cases.
The first line of each test case contains two integers n$$n and (1 \leq k \leq n \leq 2 \cdot 10^5$$1 \leq k \leq n \leq 2 \cdot 10^5) — the length of the paper and the integer used in the operation.
inputCopy
8
6 3
WBWWWB
7 3
WWBWBWW
5 4
BWBWB
5 5
BBBBB
8 2
BWBWBBBB
10 2
WBBWBBWBBW
4 1
BBBB
3 2
WWW
outputCopy
2
1
2
1
4
3
4
0