Thomas 想要从 Liza 那里购买 $n$ 杯拉面。她有两种 Thomas 喜欢的品牌：品牌 A 和品牌 B。每个品牌都销售不同规格的拉面包装。对于每个整数 $k \ge 1$，都有一个大小为 $k$ 的品牌 A 包装，其中包含 $k^2$ 杯拉面；以及一个大小为 $k$ 的品牌 B 包装，其中包含 $2k^2$ 杯拉面。

Liza 的库存中每种类型的包装各有一个。你的任务是确定 Thomas 如何从 Liza 那里购买恰好 $n$ 杯拉面，或者指出这是不可能的。

注意，你不需要最小化包装的数量。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例包含一行，其中有一个整数 $n$ ($1 \le n \le 10^9$)，表示 Thomas 想要从 Liza 那里购买的拉面杯数。

输出格式

对于每个测试用例，输出一行。

如果 Thomas 无法从 Liza 那里购买 $n$ 杯拉面，直接输出 0。

否则，输出一个正整数 $k$，随后列出 $k$ 个包装类型。包装类型由一个字母（A 或 B）表示品牌，后跟一个表示其大小的正整数。所有包装的拉面杯数之和应为 $n$，且每种包装类型不得出现超过一次。

样例

输入 1

4
1
10
12
20

输出 1

1 A1
2 A1 A3
2 A2 B2
4 A3 B2 B1 A1

说明

在第一个测试用例中，Thomas 只从 Liza 那里购买了 A1 包装，总计 $1^2 = 1$ 杯。

在第二个测试用例中，Thomas 可以从 Liza 那里购买 A1 和 A3 包装，总计 $1^2 + 3^2 = 10$ 杯。

在第三个测试用例中，Thomas 可以从 Liza 那里购买 A2 和 B2 包装，总计 $2^2 + 2 \times 2^2 = 12$ 杯。

在第四个测试用例中，Thomas 可以从 Liza 那里购买 A3、B2、B1 和 A1 包装，总计 $3^2 + 2 \times 2^2 + 2 \times 1^2 + 1^2 = 20$ 杯。