题目描述

在桥梁还不普及的年代，人们使用渡船将汽车运送到河对岸。与大型渡船不同，河流渡船依靠引导索和河流的水流动力运行。汽车从渡船的一端驶入，渡船穿过河流，汽车从渡船的另一端驶出。

有一艘长度为 $l$ 米的渡船在河上往返行驶。汽车可能会到达河的两岸中的任意一岸，等待渡船将其运送到对岸。只要渡船上载有汽车，或者至少有一岸有汽车在等待，渡船就会持续在两岸之间往返行驶。每当渡船到达一岸时，它会卸下船上的汽车，并尽可能多地装载等待过河的汽车（按照汽车到达的顺序装载），只要这些汽车能够放在甲板上。渡船的甲板只能容纳一排汽车。渡船最初停在左岸，但由于故障需要修理，修理花费了很长时间。在此期间，两岸都形成了等待过河的汽车队伍。

输入格式

第一行输入一个整数 $c$，表示测试用例的数量。每个测试用例的第一行包含两个整数 $l$ 和 $m$。接下来的 $m$ 行按顺序描述等待运输的汽车，每行给出汽车的长度（以厘米为单位）和汽车所在的河岸（“left”或“right”）。

输出格式

对于每个测试用例，输出一行，表示渡船需要穿过河流多少次才能运送完所有等待的汽车。

输入样例 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

输出样例 1

3
3
5
6

来源

Waterloo Local Contest, 2006.5.27