Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2118
Christopher's Rainy Day

Time Limit: 5 Seconds      Memory Limit: 32768 KB

As you've known in "Christopher's Key Ring" problem, Christopher nearly spent all of his money being treated in the hospital. The only thing left to him, is the heart filled with recollection, and fighting with tragic Fortune's wheel. He loves animals, especially cats and dogs, so he...

Christopher's pet shop is the biggest one in XX city. It has even 250,000 pets at the most prosperous time. One day, a rich man came to buy all of his cats and dogs. Christopher thought this is the best time to turn over a new leaf. But the rich man said, he'll pay money iff he sees the entire N arrived pets in good condition.

Transporting them is a difficult problem, coz he only has N pets (dogs and cats), none of them could be done harm. There's a train with several carriages waiting for them. If a carriage has much more cats than dogs, or much more dogs than cats, they might fight together (to ensure their safe, the max difference between numbers of cats and dogs must not exceed k). Apparently a carriage with only cats or only dogs is allowed.

The number of cats and dogs is so large that Christopher couldn't pick a single cat or dog among them. They must get on the train one by one, from the first carriage to the last. That is, if he's filling Xth carriage, he could put the current pet onto the Xth carriage, or close the door of Xth carriage (make sure this carriage is allowed depending on the above paragraph), and put it onto the (X+1)th carriage.


Input

The first line of input contains a number X which denotes the number of test cases. For each test case:

Line 1: 3 integer n (n <= 250,000) - number of cats and dogs, m - the capacity of one carriage, k - the max difference between number of cats and dogs on a single carriage. (1 <= m, k <= n)

Line 2~n+1: every line contains a character ('C' or 'D'), denotes the type of a pet in queue.

There're NO breakline between two continuous test cases.


Output

Exact X lines, each one contains the minimal number of carriages needed.


Sample Input

2
5 4 1
C
D
D
D
C
5 4 1
C
D
D
D
C


Sample Output

2
2


(adviser)
Site: http://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm


Author: XIN, Tao
Source: Online Contest of Christopher's Adventure
Submit    Status