Network Connection

Jongbin is the chairman of a very large group that runs $N$ companies numbered from $1$ to $N$. At the start, every company has its own independent computing and communication center, so it forms a cluster by itself, and that company is the center of its own cluster.

To improve their services, Seohyun, the group's CTO, designed the following procedure for merging clusters into larger ones that can be managed from a single center:

1. Pick a company $I$ that is currently the center of some existing cluster $A$.
2. Pick a company $J$ that belongs to a different cluster $B$ (so $B \neq A$; $J$ need not be a center).
3. Connect $I$ and $J$ with a communication line. The length of this line is $|I - J| \bmod 1000$.
4. Clusters $A$ and $B$ merge into one new cluster, and the center of the new cluster is the center of $B$.

While these merges are happening, people keep asking how far a given company currently is from the center of its cluster, measured as the total length of the lines along the path from that company to the center. Write a program that carries out the merges and answers these distance queries.

The input consists of several test cases. The first line contains the number of test cases $T$. Each test case begins with $N$ ($4 \le N \le 20000$), the number of companies. Then several lines follow, each holding one of the two commands below:

• E I — output the distance from company $I$ to the center of its current cluster.
• I I J — connect center $I$ to company $J$ (perform one merge as described above).

Each test case ends with the single letter O. In each test case the total number of commands does not exceed $200000$, and the number of I commands is fewer than $N$.

For each E command, print the requested distance on its own line.