Nanami 是从树上来的天使。
有一个 n 个节点的树，树上存在一个特殊节点 m。Nanami 和你在这个树上玩一个游戏，在每次操作中，你们都必须选择存在的树的部分上的一条边，删除这条边并将树分成两部分，保留有特殊节点 m 的那部分并且删除另外一部分。当树只剩一个节点时，就无法删除边了，那么此时的操作者输掉游戏。
在每次游戏中，Nanami 先手，两人轮流操作，已知两人每轮都会做最优操作，那么在特殊节点 m 的编号分别为 1 到 n 的情况下，谁会赢得游戏呢？
第一行，一个整数 t(1≤t≤104)，代表数据组数。
对于每组数据：
第一行，一个整数 n(1≤n≤3⋅105)，代表树的节点个数。
接下来的 n−1 行，每行两个整数 u,v(1≤u,v≤n)，代表树上一条边，保证输入数据是一棵树。
保证同一测试点内 n 的总和不超过 3⋅105。
对于每组数据，输出一行长度为 n 的字符串 ans，第 i 个字符代表在特殊节点 m 为 i 的情况下，谁获得游戏的胜利。如果 Nanami 获得胜利，则 ans[i] 为字符 'A'；否则 ans[i] 为字符 'B'。
输入样例
4
2
1 2
3
1 2
3 2
4
1 2
1 3
1 4
4
1 2
4 2
3 4
输出样例
AA
ABA
AAAA
AAAA