DWITE, January 2012, Problem 4

Little Alice and Little Bob are playing with their favourite toys, Lego blocks. They have ~N~ blocks of various heights, arranged in a row. They decide to play a game with their blocks.

Alice and Bob take turns removing one Lego block from the row, with Alice going first. At the beginning of a player's turn, if the blocks form a ladder – a sequence of either non-increasing or non-decreasing heights – that player loses. Given the heights of the initial row of blocks, determine who has the winning strategy, if they play optimally.

The input will contain 5 test cases, and each test case describes 3 games. The first line of each game contains a number ~N~ (~1 \le N \le 15~), the number of blocks in that game. The next line contains ~N~ space-separated integers, representing the heights of the blocks, which will be integers from ~0~ to ~100~ inclusive.

The output will contain 5 lines, with strings of 3 characters each. The ~i^\text{th}~ character of the ~j^\text{th}~ line should represent the result of the ~i^\text{th}~ game of the ~j^\text{th}~ test case: A if Little Alice wins, and B if Little Bob wins.

Sample Input

2
2 3
3
0 2 2
4
1 2 4 3

Sample Output

BBA

Problem Resource: DWITE