The Institute of NITT believes in frugality. So when they made the plan for interconnecting the N hostels, they decided to construct as few bidirectional roads as possible. The hostels are interconnected with roads in such a way that every pair of hostels is connected by exactly one path.

Moreover, they were so frugal that they used low quality tar in making the roads. As a result, the roads start to crack and cannot be used anymore.

Now Alpa has a set of queries. At the time of each query, he knows the roads that are un-usable. He wants to find the number of pairs of hostels that are disconnected, i.e, the number of pairs (x,y) such that 1 <= x < y <= N and there exists no path between hostels x and y.

Help him find the result for each query.

Constraints:

Test cases <= 5

No. of hostels, N <= 20000

No. of queries, Q <= 20000

Input

First line contains t, the total test cases.

Each test case looks  as follows:

First line contains N, total number of hostels.

Next N - 1 lines contain two integers x and y, indicating that there is a road  between x and y. (1 <= x < y <= N). The roads are numbered from 1 to N - 1.

Next line contains Q, total number of queries.

Next Q lines contain the Q queries.

Each query may be of the following two forms:

R x - Remove the road numbered x. It is guaranteed that this road existsand hasn't already been removed.

Q - Output the total number of pairs (x, y) such that 1 <= x < y <= N and there exists no path between hostels x and y.

Output

For each test case,

Output a line for each query with the required value.

Print a blank line after each test case.

 

Example

Input:
2

3
1 2
1 3
5
Q
R 1
Q
R 2
Q
4
1 2
1 3
1 4
7
Q
R 1
Q
R 2
Q
R 3
Q

Output:
0
2
3
0
3
5
6</span>

</p>