A. Nanami and Subtree of Tree
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There is a $$$n$$$-node tree with a special node $$$m$$$, Alice and Bob play a game on this tree, in which in each operation they must select an edge on the part of the tree where it exists, delete the edge and split the tree into two parts, keeping the part with the special node $$$m$$$ and deleting the other part. When there is only one node left in the tree, it is not possible to delete the edge, and the operator loses the game.

In each game, Alice starts, and the two players take turns, knowing that they will do the optimal operation in each round, so who wins the game if the special nodes $$$m$$$ are numbered from $$$1$$$ to $$$n$$$, respectively?

Input

In the first line, an integer $$$t(1\le t \le 10^4)$$$, representing the number of data sets.

For each group of data:

The first line, one integer $$$n(1\le n \le 3·10^5)$$$, represents the number of nodes in the tree.

For the next $$$n-1$$$ rows, two integers $$$u,v(1\le u,v \le n)$$$ per row, representing one edge of the tree, ensuring that the input data is a tree.

It is guaranteed that the sum of $$$n$$$ within the same test point does not exceed $$$3·10^5$$$.

Output

For each set of data, output a line of string $$$ans$$$ of length $$$n$$$, with the $$$i$$$ th character representing who wins the game if the special node $$$m$$$ is $$$i$$$. If Alice wins, $$$ans[i]$$$ is the character 'A'; otherwise $$$ans[i]$$$ is the character 'B'.

Example
Input
4
2
1 2
3
1 2
3 2
4
1 2
1 3
1 4
4
1 2
4 2
3 4
Output
AA
ABA
AAAA
AAAA