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