There is a growing tree, which has only one node on Day . This node is the root of the tree, numbered  and colored .

On each of the following  days, one of the two types of events below will happen, each of which is described by three integers :

, which means node  grows a new leaf  colored . Or formally, a new node numbered  and colored  is linked to node , where  is the number of nodes of the tree at the end of the previous day.

, which means you want to count the number of nodes colored  in the subtree rooted at node .

For each type-2 event, output the answer. Please note that the input is encoded.

输入描述:

The first line of the input contains an integer , representing the number of test cases.

The first line of each test case contains two integers , representing the color of node  and the number of events.

Each of the following  lines of each test case contains three integers , which has been encoded. You should decode it to get real input  with equations: , , , where  is the answer of the last type-2 event or  if there is no type-2 event before in this test case,  is the number of nodes of the tree at the end of the previous day, and  is bitwise-xor operation.

It is guaranteed that the sum of  over all test cases does not exceed .

输出描述:

For each type-2 event, output the answer in a single line.

2
1 3
1 1 2
1 1 1
2 1 1
1 7
2 1 2
1 1 2
2 1 1
0 3 0
0 0 3
3 2 0
3 0 3

2
0
1
1
2

Here is the decoded input of the example:
2
1 3
1 1 2
1 1 1
2 1 1
1 7
2 1 2
1 1 2
2 1 1
1 2 1
1 1 2
2 3 1
2 1 2