Magical Tree Queries

You are given a magical tree that starts with a single root node having ID 1 and a depth of 0. You will receive a series of instructions to build this tree and answer queries about the depth of certain nodes.

There are two types of instructions:

• ADD a b: Attach a new node with ID b as a child of an existing node with ID a. The new node's depth is the depth of node a plus 1.
• QUERY x: Query the depth of the node with ID x in the tree.

The instructions for multiple test cases are provided in a single input. The first line contains an integer T which denotes the number of test cases. For each test case, the first line contains an integer N (the number of instructions), followed by N lines each containing one instruction. Print the result for each QUERY instruction in the order they appear, each on a new line.

The mathematical relationship can be summarized as follows: if a node b is added as a child of node a, then its depth is given by:

\(depth(b) = depth(a) + 1\)

inputFormat

The input is provided from stdin and has the following format:

T
N1
instruction1
instruction2
... 
instructionN1
N2
instruction1
instruction2
... 
instructionN2
...

Where:

• T is the number of test cases.
• For each test case, N represents the number of instructions.
• Each instruction is either in the format ADD a b or QUERY x.

outputFormat

Print the result of each QUERY instruction on a new line to stdout.

## sample

1
5
ADD 1 2
ADD 1 3
ADD 2 4
QUERY 4
QUERY 3

2
1

</p>