CodeClash là một trò chơi trực tuyến được sáng lập bởi Antony. Trò chơi được ưa chuộng trong giới lập trình vì độ đơn giản trong cách chơi và các giải thưởng mà người chơi có thể đạt được. Mỗi ván chơi CodeClash có luật như sau:

• Một ván chơi chỉ có đúng \(2\) người chơi tham gia. Ban đầu mỗi người chơi có số điểm là \(0\).
• Một ván chơi được chia thành nhiều hiệp, mỗi hiệp hai người chơi sẽ đấu với nhau để chọn ra đúng một người chiến thắng. Người chiến thắng một hiệp sẽ được cộng \(1\) điểm vào tổng điểm. Người thua không được điểm nào. Không có hiệp đấu hòa.
• Trò chơi kết thúc ngay khi một trong hai người đạt tới điểm \(5\). Khi đó người có điểm số \(5\) sẽ giành chiến thắng chung cuộc.

Vì Antony là một người có tính keo kiệt nên anh không chia sẻ trò chơi cho bất cứ ai khác, vì vậy trò chơi này chỉ có thể chơi trên server của anh ấy. Lợi dụng việc này, các hacker đã cùng nhau hợp lực tấn công vào server của Antony và xóa đi một phần dữ liệu các ván đã chơi trên server của Antony.

Cụ thể hơn, mỗi ván chơi với một cặp người chơi A và B được Antony lưu bằng một xâu ký tự, với ký tự thứ \(i\) bằng A khi và chỉ khi người A dành chiến thắng trong hiệp đấu thứ \(i\), ngược lại ký tự thứ \(i\) bằng B. Có tổng cộng \(T\) ván bị các hacker xóa đi một số ký tự đầu tiên (không xóa hết) trong dữ liệu, dẫn đến trên server chỉ còn dữ liệu của \(n_i\) hiệp cuối cùng của ván thứ \(i\).

Yêu cầu: Với mỗi ván chơi trong \(T\) ván bị mất dữ liệu, hãy cho biết người nào đã dành chiến thắng chung cuộc.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \leq T \leq 100\)). \(2 \times T\) dòng tiếp theo chứa dữ liệu còn lại của \(T\) ván.

Dòng thứ \(2i\) (\(1 \leq i \leq T\)) chứa một số nguyên dương \(n_i\) (\(1 \leq n_i < 10\)) là số hiệp mà ván thứ \(i\) vẫn còn dữ liệu

Dòng thứ \(2i + 1\) (\(1 \leq i \leq T\)) chứa một xâu ký tự \(s_i\) độ dài \(n_i\) miêu tả dữ liệu còn sót lại của ván chơi thứ \(i\). Hai người chơi trong tất cả các ván đều lần lượt được biểu diễn bằng các chữ cái A và B.

Dữ liệu đảm bảo các ván chơi được cho luôn hợp lệ.

OUTPUT FORMAT

In ra \(T\) dòng, dòng thứ \(i\) chứa một chữ cái duy nhất là A hoặc B cho biết người chiến thắng trong ván thứ \(i\).

Ví dụ:

Input

2
7
ABAAABA
9
BABABABAB

Output

A
B

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House