HZ has lights, and he puts the lights to form a matrix of rows and columns, so each element of the matrix is a light. Initially, all the lights are off. There is a robot which can perform these three kinds of operations:

R : Switch the states of all the lights in the -th row.
C : Switch the states of all the lights in the -th column.
D: Switch the states of all the lights on the main diagonal. We say that a light is on the main diagonal if and only if its row index is equal to its column index.

Switching the state of a light means to turn it on if it was off, or turn it off if it was on.

Now you are given operations in order, and you need to answer how many lights are on after each operation.

The first line of input contains an integer , denoting the number of test cases.
For each test case, the first line contains two integers . ()
In the following  lines, each line is "R " or "C " or "", denoting an operation. ()
It's guaranteed that the sum of  of all the  test cases is no more than .

For each test case, print  lines, denoting the number of lights on after each operation.

1
3 6
R 2
C 2
D
R 1
R 2
D

3
4
7
6
3
4