Haunted Hallway

There’s a circular hallway with $N$ cells (numbered from $0$ to $N - 1$ ) and $M$ ghosts.
Each ghost is denoted by its starting position and direction, e.g. 5R means "position 5, facing right".

All ghosts move at the same pace: every second, each one steps in the direction it faces. Movement is cyclic:

If a ghost at position $0$ moves left (L), it goes to position $N - 1$ .
If a ghost at position $N - 1$ moves right (R), it goes to position $0$ .

Two ghosts can collide in either of the following scenarios:

If they land on the same cell at the same time.
Or if they pass each other in one step (like one moving $7 \to 8$ while another moves $8 \to 7$ ).

Determine whether any two ghosts will ever collide, or if they will keep wandering forever without meeting.

Input

The first line contains an integer $T$ — the number of test cases.

Each test case:

One line with two integers $N$ and $M$ ( $2 \leq N \leq 100$ , $2 \leq M \leq 10$ ).
One line with $M$ tokens of the form <position><direction>, where <position> is an integer $0 \leq P < N$ and <direction> is L or R.
All positions are distinct.

Output

For each test case, print Case #i: YES if any two ghosts will ever collide for test $i$ , and Case #i: NO otherwise.

Example

Input

3
5 2
1R 3L
4 2
0L 3R
6 3
2R 0R 4R

Output

Case #1: YES
Case #2: YES
Case #3: NO

Explanation

Case 1: 1R and 3L move toward each other immediately and collide.
Case 2: With $N = 4$ , 0L moves to 3, while 3R moves to 0. Thus, they collide in the middle.
Case 3: The hallway is $N = 6$ cells long, with three ghosts moving to the right. They will continue moving in unison for all eternity.