题目描述

汉诺塔问题是一个十分经典的问题。

即有三根杆子 A，B，C。 A 杆上有 n 个穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆： 1.每次只能移动一个圆盘 2.大盘不能叠在小盘上面

因为汉诺塔问题的最优步骤唯一，所以实际上每一步是固定的。

那么，对于最优步骤的第 k 步后而言，汉诺塔此时每个圆盘处于哪个杆子。

输入格式

本题有 T 组测试样例，以下为每组测试样例的输入情况。 第 1 行 1 个整数 n，表示穿孔圆盘的个数; 第 2 行 1 个长度为 n 的 01 字符串 k，表示二进制下小度想要查询的第 k 步后的汉诺塔情况。 数据范围保证 T≤100 , 1≤Σn≤1e5 , 0≤k≤最优步数。

输出格式

输出 1 个长度为 n 的字符串，字符串中仅包含 ABC 三种字符，分别代表第 i 小的圆盘所在的杆子编号。

2
3
011
5
11111

BBA
CCCCC