题目描述

OITV电视台最近开设了名为“免费超市”的真人电视节目，在节目中，抽奖选拔的民间志愿者们将随机匹配进行两两对抗赛。每场比赛上，节目组设置n件商品排成一排供选手挑选，两名选手将交替出手选中并拿走商品，每件商品有着不同的价值 $a_i$，商品取完后总价值较高的选手即为本局比赛胜利者，将获得节目组的额外奖励。

为了增加趣味性，节目组规定选手出手时只能在一排商品两端的两个商品中选择一个并拿走。可以预见的是，若两名选手足够聪明，那么比赛存在着“先手必赢”或“后手必赢”的局面，现在节目组想要知道每局比赛理论上的胜负局面（假定选手都会尽量让自己所得价值最大）。

输入输出格式

输入格式：

• 第一行输入一个数 t，表示比赛局数
• 每轮游戏下：
  • 第一行输入一个数 n，表示本轮比赛的商品数
  • 第二行输入空格隔开的 n个数 $a_i$，表示商品价值

输出格式：

• 对于每局比赛输出一行一个字母，表示该轮比赛理论结果。（'A'表示先手赢，'B'表示后手赢，平局视为先手赢）

输入输出样例

输入样例：

3
4
1 4 100 5
5
1 9 3 8 7
6
1 2 3 3 2 1

输出样例：

A
B
A

样例说明：

第一场先手玩家拿1+100=101分，后手玩家拿5+4=9分； 第二场先手玩家拿7+3+1=11分，后手玩家拿8+9=17分； 第三场两名玩家均为6分。

测试点

10个测试点，每个测试点得10分。

每个测试点时间限制1s，内存限制128MB。

数据范围：

• 对于20%的数据：$1<=n<=20$；
• 对于60%的数据：$1<=n<=200$；
• 对于100%的数据：$1<=t<=10、1<=n<=10​^3、1<=a​_i<=10^4$ 。