Rút gỗ

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.

Dữ liệu vào

• 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.

Dữ liệu ra

Ghi trên $q$ dòng, mỗi dòng là kết quả mỗi ván chơi: in A nếu người A thắng, in B nếu người B thắng.

Ràng buộc

• $1\le q\le 10$.
• $1\le n\le {10}^5$.
• $0\le a_i\le {10}^{18}$.

Subtasks

• Subtask 1 ($40\%$ số điểm): $n,a_i\le 2000$.
• Subtask 2 ($30\%$ số điểm): $n\le {10}^5$; $a_i\le {10}^6$.
• Subtask 3 ($30\%$ số điểm): $n\le {10}^5$; $a_i\le {10}^{18}$.

Ví dụ