珅泽教育的小婷老师正在组织一项队列实践，她请小泽按下面的规则完成记录。

有多组渡船装载。渡船长度为 $L$ 米，初始在左岸。每辆车给出长度（厘米）和等待岸边。每次渡船在当前岸按到达顺序装车，直到下一辆车放不下或该岸无车，然后驶向对岸；不能跳过队首去装后面的短车。

请输出运完全部车辆需要的航行次数。

输入格式

第一行输入测试组数 C。

每组先输入 L,M，接下来 M 行输入车辆长度和 left 或 right。

输出格式

每组输出最少航行次数。

1
6 7
571 right
234 left
243 left
163 right
558 left
142 left
124 right

5

1
7 9
91 right
97 left
594 left
641 right
386 left
422 left
101 right
206 left
364 left

7

1
8 11
389 right
393 left
510 left
728 right
584 left
160 left
459 right
205 left
262 left
456 right
387 left

9

数据范围与约定

• $1 \le L \le 100$
• $1 \le M \le 10^4$
• 每辆车不长于渡船