Một ván chơi rút gỗ có ~n~ cột gỗ, cột thứ ~i~ có ~a_i~ thanh gỗ ~(a_i \ge 0)~. Hai người A và B chơi luân phiên, A đi trước. Tại mỗi lượt, người chơi chọn một cột ~i~ bất kỳ đang có ít nhất ~2~ thanh gỗ và rút đi không quá một nửa số thanh hiện có của cột đó. Người không thể thực hiện bất kỳ nước đi hợp lệ nào thì thua. Biết cả hai người đều chơi tối ưu.

Yêu cầu: Có ~q~ truy vấn, mỗi truy vấn là một ván chơi. Hãy xác định người thắng ở mỗi truy vấn.

Input

• Dòng ~1~: số nguyên ~q~ ~(1 \le q \le 10)~;

• Tiếp theo là ~q~ truy vấn, mỗi truy vấn gồm ~2~ dòng:

  • Dòng đầu: số nguyên ~n~ ~(1 \le n \le 10^5)~;

  • Dòng tiếp theo: ~n~ số nguyên ~a_1, \dots, a_n~ ~(1 \le i \le n; 0 \le a_i \le 10^{18})~.

Các số trên cùng một dòng cách nhau bởi một dấu cách.

Output

Ghi trên ~q~ dòng, mỗi dòng là kết quả mỗi ván chơi.

Scoring

Sample Input 1

2
2
3 2
3
2 3 2

Sample Output 1

A
B