A. Olives and Water
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baran has a strip of land in the beautiful city of Afrin, a city renowned for its delicious olive oil, lush green nature, and generous people. Visitors to Afrin are always captivated by its stunning scenery.

Baran's land is represented as a single line of $$$n$$$ cells. Each cell can be in one of four states:

  • Empty ('.')
  • A fruitful olive tree ready for harvest ('O')
  • A tree that needs water ('T')
  • A bag of water ('W')

Baran plans to walk along this line of cells exactly once, from the first cell to the last. He has a vehicle that can carry a total of $$$M$$$ kilograms of items. For simplicity, we assume one bag of water weighs 1 kg and one unit of harvested olives also weighs 1 kg.

During his single pass, Baran has two objectives:

  1. He must water every single tree that needs it. To water a tree at cell $$$i$$$, he must have a bag of water in his vehicle. He must have picked up this bag from a cell $$$j \lt i$$$. Upon use, the bag of water is consumed and removed from the vehicle.
  2. He wants to collect the maximum possible amount of olives. He can choose to harvest any fruitful olive tree he encounters, which adds one unit of olives to his vehicle.

The total weight of water bags and olive units in his vehicle cannot exceed $$$M$$$ at any point in time.

Can you help Baran determine the maximum number of olive units he can collect while ensuring all needy trees are watered?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^5$$$). The description of the $$$T$$$ test cases follows.

The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le M \le 10^5$$$), representing the number of cells in the land and the vehicle's capacity, respectively.

The second line of each test case contains a string of length $$$N$$$, describing the land. Each character is one of ., O, T, or W.

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

Output

For each test case, print a single integer on a new line. This integer should be the maximum number of olive units Baran can collect. If it is impossible to water all the trees that need it, print -1.

Example
Input
4
8 2
.OOWTWTO
7 2
TOOWTWT
5 3
.OOOO
12 3
OWWTWTTOOOOO
Output
2
-1
3
3
Note

First Test Case:

  • At index 2, he takes the first 'O'. Vehicle weight becomes 1.
  • At index 4, he takes 'W'. Vehicle weight becomes 2.
  • At index 5, he uses 'W' to water the tree at index 5. Vehicle weight becomes 1.
  • At index 6, he takes 'W'. Vehicle weight becomes 2.
  • At index 7, he uses 'W' to water the tree at index 7. Vehicle weight becomes 1.
  • At index 8, he takes 'O'. Vehicle weight becomes 2.

The number of 'O's inside the vehicle is 2, so the answer is: $$$2$$$

Second Test Case:

  • At index 1, there is a 'T', but he doesn't have any 'W'.
  • Therefore, he cannot water the tree at index 1.

The answer is: $$$-1$$$

Third Test Case:

  • He takes the 'O's from indices 2, 3, and 4. Vehicle weight becomes 3.
  • At index 5, he cannot take the 'O' because the vehicle weight is equal to $$$m$$$.

The answer is: $$$3$$$

Fourth Test Case:

  • At index 1 he takes the first 'O'. vehicle weight becomes 1.
  • At index 2,3 he takes the 'W'. vehicle weight become 3 , the vehicle has 1 'O' and 2 'W'.
  • at index 4 he use one from 'W' vehicle weight become 2 , the vehicle has 1 'O' and 1 'W'.
  • at index 5 he he takes the 'W' vehicle weight become 3 , the vehicle has 1 'O' and 2 'W'
  • at index's 6,7 he use 2 from 'W' vehicle weight become 1 , the vehicle has 1 'O' only.
  • at index's 8,9 he takes 2 'O' vehicle weight become 3 ,the vehicle has 3 'O' only.
  • at index's 10,11,12 he can't take any 'O' because the vehicle weight is equal to $$$m$$$. the answer is: $$$3$$$