汉诺塔

设有 $n$ 个大小不等的圆盘，按从小到大的顺序从 $1$ 到 $n$ 编号。有三根立柱，立柱的编号分别为 $A,B,C$，刚开始所有圆盘都在立柱 $A$ 上，并且大圆盘在下、小圆盘在上。

现在要求找到一种步数最少的移动方案，使得移动全部完成后，所有圆盘都在立柱 $C$ 上，并且大圆盘在下小圆盘在上。

移动时有如下要求：

• 一次只能移一个盘；
• 不允许把大盘移到小盘上面。

以下为 $n=3$ 时的示意图：

$q$ 次询问，每次给定 $n$ 和 $k$，求 $n$ 个盘子的汉诺塔问题的第 $k$ 次移动是把哪个盘子从哪根柱子移动到哪个柱子

输入格式

第一行，一个正整数表示 $q$

对于每个询问输入一行：

包含两个数 $n, k$，特殊地，$k$ 以 $n$ 位二进制数形式给出

输出格式

输出 $q$ 行，每行先输出一个正整数表示这一步移动的盘子编号，再输出两个字母表示从哪根柱子移动到哪根柱子，三者之间均用一个空格隔开

输入输出样例

输入 #1

10
2 01
2 10
2 11
3 001
3 010
3 011
3 100
3 101
3 110
3 111

输出 #1

1 A B
2 A C
1 B C
1 A C
2 A B
1 C B
3 A C
1 B A
2 B C
1 A C

数据范围

对于 $20 \%$ 的数据，$1 \leq n \leq 20$

对于 $40\%$ 的数据，$1 \leq n \leq 30$

对于 $60\%$ 的数据，$1 \leq n \leq 60$

对于 $100\%$ 的数据，$1 \leq q \leq 10, 1 \leq n \leq 10^5, 1 \leq k < 2^{n}$