UP 100

Time Limit: 1 Second    Memory Limit: 32768 KB

Sunny Cup 2003 - Preliminary Round

April 20th, 12:00 - 17:00

Problem F: UP 100

UP 100 is a challenging game where you take the role of a boy advancing in a 40-unit-wide space with walls on both sides.

As the game starts, the boy moves at 2 units per second to the right. You can only make jumps. It acts like: you press the "space" key for some time, and the force f will increase 2 units per second starting from 0. The force wraps back to 0 when it exceeds 8. When you release the key, the boy jumps up according to the force. If f = 8, v = 16, otherwise v = f. (We simple assume you shall only press and release the bar at integral seconds. The game starts at 0-th second, and the boy can jump from any integral position on level 0.) When the boy is in space, he still advances at 2 units per second horizontally (he should change direction when bumping into the wall), and he moves at 2 units per second upwards till he reaches a height of v (he can penetrate any bars in space). After that, he moves down at 2 units per second until he lands on a bar. When he lands, the force becomes 0.

There are 4 types of bars:

b for short. This bar is for holding purpose only.
s for short. This bar doubles v when jumping.
lp for short. This bar contributes a 1-unit-per-second-to-the-left velocity to the object on it.
rp for short. This bar contributes a 1-unit-per-second-to-the-right velocity to the object on it.

All the bars are 8 units long. None of them shall intersect with each other.
Given such a configuration, please estimate the highest bar the boy could reach. Notice it will not be greater than n of course.

Input

First line of input contains T, the number of tests to process. For each test:

The first line contains n (0 < n <= 500), the upper bound of the space.

The second line contains m (0 <= m <= 500), the number of bars.

The next m lines are in the format type height left (1 <= height <= n, 0 <= left <= 32).

Output

For each test, prints the maximum height on a single line.

Notice the lowest is the 0-th level. The highest is the n-th level. The 0-th level is ground. lp and rp will not touch with the wall or any other bar.

Sample Input

2
10
0
7
2
b 4 4
lp 2 2

Sample Output

0
4

Submit

Source: Zhejiang University Local Contest 2003, Preliminary