You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

lyk同学在上数据结构这门课时，计算了汉诺塔问题（不了解的同学见题目最下方）的最少挪动次数，他觉得太简单了。于是他加决定大难度考考 wlm 同学。 lyk 的问题如下： 有n个盘子，初始时全部位于 A 柱，需要按照汉诺塔的规则，在最少挪动次数下，将所有盘子移动到 C 柱。 问第k次挪动是从哪个柱子挪到哪个柱子？ wlm 急着考六级，他把这个问题交给了身为 ACM 皇弟的你，他说如果你做出来了，他就变成奶龙跟你合影。 由于你非常想见识一下奶龙版 wlm🤮，所以你一定会把这道题做出来。

你的任务是：

在保证整个过程在最少挪动的前提下，对于给定的n和k，输出第k次移动是从哪根柱子移动到哪根柱子。 三根柱子分别命名为大写字母 A、B、C。 保证答案唯一。

Input Format

输入的第一行包含一个整数T，表示测试用例的数量。 接下来是T个测试用例，每个测试用例一行，包含整数n和二进制字符串k：

• n：盘子的数量；

• k：要求询问的第k次挪动（k从1开始编号，由于k可能很大，题中k使用二进制字符串表示）。

保证对每个测试用例：

• 初始时，所有n个盘子都在 A 柱上，按从下到上的顺序盘子越来越小；

• B、C 两根柱子最开始为空；

• 全程必须满足汉诺塔规则（任意时刻都不能把大盘子压在小盘子上）；

• 解法是将所有盘子从 A 柱移动到 C 柱的最少步数解；

Output Format

对于每个测试用例，输出一行（共T行），格式如下：

U V

其中：

• U表示第k次移动时的起始柱子（A、B 或 C）；

• V表示第k次移动时的目标柱子（A、B 或 C）。

Sample

输入输出样例 #1

输入 #1

3

1 1

3 100

3 10

输出 #1

A C

A C

A B

样例解释

• 对于第一个测试用例：

n = 1，只需要挪动一次：

A → C

所以第 1 步就是 A C。

• 对于第二个测试用例：

n = 3 时，最优解需要挪动7次：

1. A → C
2. A → B
3. C → B
4. A → C
5. B → A
6. B → C
7. A → C

所以第 4 步是 A → C，输出 A C。

• 对于第三个测试用例：

同样是 n = 3，第 2 步是 A → B，输出 A B。

Hint

数据范围

• 1<=T<=1000

• 1<=n<=10000

• 对每个测试用例，保证 1<=k<=2^n-1

汉诺塔问题描述：

• 有三根柱子：A、B、C。

• 初始时A 柱上有n个大小各不相同的圆盘，从下到上越盘越小，B、C上没有圆盘。

• 目标：把这n个盘子全部从 A 挪到 C。

要求遵守两条规则：

1. 每次只能移动一个盘子。
2. 任意时刻都不能把 大盘子压在小盘子上。