A. The Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On a sunny Saturday morning, Oliver and Armando, enthusiastic members of the "Algorithm Club 2880", decided to spend a healthy day at Lincoln Park. After intense sessions of pull-ups on the park bars, they decided to take a break and satisfy their appetite with some Greek yogurt. They set off to the nearest store, chatting animatedly about their physical feats.

As they made their way to the store, their attention was captured by an ancient tree with a peculiar appearance. The tree, with its twisted branches and leaves whispering stories of the past, seemed to hide a mystery. Armando, always curious, suggested they take a break and play a game in which the tree would be the setting.

Intrigued by the idea of a spontaneous game in the middle of the park, Oliver accepted the challenge. Armando explained the rules: "Here, each player takes turns, the root of the tree is node $$$1$$$. I start from the root and choose a neighbor, then you will choose a neighbor of the node I chose, and so on. The player who can no longer choose a neighbor of the current node loses. Also, you should know that you cannot choose a node that we had previously chosen."

With a smile on his face, Oliver turned to you and said,"Friend, I need your help to win this game! Can you tell me if, with an optimal strategy, I will win? It would be great to take the victory in this random challenge!"

Input

The first line contains an integer $$$t(1\le t\le 10^5)$$$ the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(2\le n \le 10^5)$$$, where $$$n$$$ is the number of nodes in the tree.

The following $$$n-1$$$ lines contain the description of the tree. Each line contains two integers $$$a_i$$$, $$$b_i$$$ $$$(1 \le a_i, b_i \le n, a_i \neq b_i)$$$, indicating that there is an edge between node $$$a_i$$$ and node $$$b_i$$$ (it is guaranteed that the edges form a tree, a graph in which there is a unique path between each pair of nodes and that also does not contain cycles).

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$10^5$$$.

Output

For each test case, print "O" if Oliver can win the game with the optimal strategy, otherwise print "F".

Example
Input
5
2
1 2
3
1 2
3 2
3
1 2
1 3
4
1 2
1 3
2 4
5
1 2
2 3
1 4
4 5
Output
F
O
F
F
O