3282 Ferry Loading IV

原文

時間制限:1000ミリ秒
メモリ制限:65536KB

問題

橋が一般的に使われるようになるまでは、車が川を渡るためにはフェリーが使われていました。フェリーは決まった経路を通り、川の流れによって動かされます。車はフェリーの一端から乗り、フェリーが川を渡り、そして車がもう一端からフェリーの外へ出ます。
今、川を渡る l メートルのフェリーがあります。車は反対岸へ渡るために、どちらかの川岸へ到着します。フェリーは、車を運んでいるか、どちらかの川岸で車が待っている限り、行ったり来たりを繰り返します。フェリーが川岸へ到着すると、搭載している車をすべて降ろし、その川岸で待っている車を、デッキに載る限り搭載します。車は到着した順番で搭載されます。フェリーのデッキは、車を１列しか搭載することができません。フェリーは最初左の川岸にいましたが、そこでフェリーは壊れてしまい、修理にいくらか時間がかかっています。その間に、両方の川岸には川を渡ろうとする車の列ができてしまいました。

入力

入力の最初の行には、テストケースの数を表すcが書かれています。それぞれのテストケースは、l, mを含む1行から始まり、到着する車を到着順に表すm行が続きます。それぞれの行には、車の長さ(センチメートル単位)と、車が到着する岸("left" もしくは "right")が書かれています。

出力

それぞれのテストケースについて、待っている車をすべて反対岸へ運ぶために何回フェリーが川を渡る必要があるかを表す1つの整数を、1行に出力してください。

入力の例

4
20 4
380 left
720 left
1340 right
1040 left
15 4
380 left
720 left
1340 right
1040 left
15 4
380 left
720 left
1340 left
1040 left
15 4
380 right
720 right
1340 right
1040 right

出力の例

3
3
5
6

出典

Waterloo Local Contest, 2006.5.27