题目背景

275307894a 和 xiexiyan 在疯狂加训博弈。

题目描述

你现在有 $n$ 张牌，初始时编号为 $1,2,3,\dots,n$，给定一个 $1\sim n$ 的排列 $p$，问要进行多少次洗牌操作才能将这副牌重洗成排列 $p$。

一次洗牌操作定义如下：

• 假设你现在有的牌序列为 $a$，另有一空序列 $b$。

• 选择一个 $p$ 满足 $1\leq p<n$，将 $a$ 序列 $[1,p]$ 下标范围内的数依次加入一队列 $q_1$，将 $[p+1,n]$ 下标范围内的数依次加入另一队列 $q_2$。

• 每次选择一个非空队列，将队首放入 $b$ 序列的末尾并弹出，重复 $n$ 次。

• 令 $a=b$，完成一次洗牌操作。

在洗牌操作的第三步中，如果你选择了 $q_1$ 的队首，则记录 A，否则记录 B。容易发现，一个长度为 $n$ 的，字符集仅有 AB 的序列唯一对应了一种洗牌方式。你需要输出最小步数以及洗牌方式。

输入格式

本题单个测试点内有多组测试数据，第一行一个整数 $T$ 表示数据组数。

对于每组数据，第一行一个整数 $n$，表示牌数。

接下来一行 $n$ 个整数 $p_i$，保证 $p$ 是一个排列。

输出格式

对于每组数据，第一行一个整数 $k$ 表示最小步数。

接下来 $k$ 行，每行一个长度为 $n$，字符集为 AB 的字符串，表示洗牌方式。

样例

样例输入 1

5
2
2 1
3
1 3 2
3
3 2 1
4
3 1 2 4
3
3 2 1

样例输出 1

1
BA
1
ABA
2
BAA
ABA
1
BAAB
2
BAA
ABA

样例 2,3,4

见下发文件，分别满足测试点 $5\sim 8,14\sim 19,20\sim 22$ 的限制。大样例输出仅提供最小步数。

提示与说明

特殊性质 A ：$p_i=(i+k)\bmod n+1$，$k$ 为一常数。

对于全部数据，满足 $2\leq n\leq 52,\sum n\leq 2\times 10^5$，保证 $p$ 构成一个排列。