lyk同学在上数据结构这门课时，计算了汉诺塔问题（不了解的同学见题目最下方）的最少挪动次数，他觉得太简单了。于是他加决定大难度考考 wlm 同学。 lyk 的问题如下： 有n个盘子，初始时全部位于 A 柱，需要按照汉诺塔的规则，在最少挪动次数下，将所有盘子移动到 C 柱。 问第k次挪动是从哪个柱子挪到哪个柱子？ wlm 急着考六级，他把这个问题交给了身为 ACM 皇弟的你，他说如果你做出来了，他就变成奶龙跟你合影。 由于你非常想见识一下奶龙版 wlm🤮，所以你一定会把这道题做出来。
你的任务是：
在保证整个过程在最少挪动的前提下，对于给定的n和k，输出第k次移动是从哪根柱子移动到哪根柱子。 三根柱子分别命名为大写字母 A、B、C。 保证答案唯一。
输入的第一行包含一个整数T，表示测试用例的数量。 接下来是T个测试用例，每个测试用例一行，包含整数n和二进制字符串k：
• n：盘子的数量；
• k：要求询问的第k次挪动（k从1开始编号，由于k可能很大，题中k使用二进制字符串表示）。
保证对每个测试用例：
• 初始时，所有n个盘子都在 A 柱上，按从下到上的顺序盘子越来越小；
• B、C 两根柱子最开始为空；
• 全程必须满足汉诺塔规则（任意时刻都不能把大盘子压在小盘子上）；
• 解法是将所有盘子从 A 柱移动到 C 柱的最少步数解；
对于每个测试用例，输出一行（共T行），格式如下：
U V
其中：
• U表示第k次移动时的起始柱子（A、B 或 C）；
• V表示第k次移动时的目标柱子（A、B 或 C）。
输入输出样例 #1
输入 #1
3
1 1
3 100
3 10
输出 #1
A C
A B
样例解释
• 对于第一个测试用例：
n = 1，只需要挪动一次：
A → C
所以第 1 步就是 A C。
• 对于第二个测试用例：
n = 3 时，最优解需要挪动7次：
所以第 4 步是 A → C，输出 A C。
• 对于第三个测试用例：
同样是 n = 3，第 2 步是 A → B，输出 A B。
数据范围
• 1<=T<=1000
• 1<=n<=10000
• 对每个测试用例，保证 1<=k<=2^n-1
汉诺塔问题描述：
• 有三根柱子：A、B、C。
• 初始时A 柱上有n个大小各不相同的圆盘，从下到上越盘越小，B、C上没有圆盘。
• 目标：把这n个盘子全部从 A 挪到 C。
要求遵守两条规则：