Are they friends?

Everyone wants to be popular! In order to be popular, it is necessary to always keep track of the current "popularity" state. I.E. We need to find out who is friends with who! Recently, to make themselves more popular, people have adopted to motto of "your friends are my friends," and vice versa. This means if A and B are friends, B and C are friends, then A and C are friends too.

This new complication creates economic opportunities! Write a program that keeps track of the now immensely complicated "popularity" state, and sell this information to those who needs it!

INPUT

There will be multiple test cases. The first line will contain an integer num equal to the number of test cases.
For each test case, the first line will contain an integer n representing the number of people we are concerned with (2 to 10000). The people are then numbered from 0 to n-1 After that, each line contains a query of the following three forms:

• f a b - this represent the newest intelligence that a and b has become friends. (0 <= a, b < n)
• q a b - this represent the newest business transcation where someone is paying to know whether a and b are friends or not.
• d - this represents the end of a dataset

Assume originally no one is friends with anyone else. Also, be prepared to handle the case of people who likes to advertise their friendships over and over again

OUTPUT

For each test case, output an integer on one line, equalling the number of "yes" replies you gave to your clients

Sample Input

1
10
f 1 5
f 2 7
q 7 1
f 3 9
f 3 9
q 9 6
f 2 5
q 7 5
d

Sample Output

1