You are given an unweighted tree that contains only 1 node. You have to process the following two types of queries:

1. \(1\ x\): Add a new node:
   You are given an already-existing node \(x\), assuming that there are \(N\) nodes in the tree till now. Now, add a new node numbered \((N+1)\) with node \(x\) as its parent.
2. \(2\ x\): You are given a node \(x\). Determine the length of the largest simple path in the tree starting from node \(x\).

For each query of type 2, you must print the required answer. Note that the length of the path is equal to the number of edges in the path.

Input format

• The first line contains a single integer \(T\ (1 \le T \le 10)\) denoting the number of test cases.
• The first line of each test contains a single integer \(Q\ (1 \le Q \le 50000)\) denoting the number of queries that you have to process.
• Each of the next \(Q\) lines contains two integers \(k\) and \(x\) \((1 \le k \le 2,\ 1\le x \le N)\) where \(N\) is the total number of nodes in the tree till now. Here, \(k\) represents a query type and \(x\) is the node number.

Output format

For each query of type 2, you are required to print the length of the largest simple path starting at node \(x\).