Hai người chơi A và B chơi trên một bàn cờ vuông kích thước \(n\times n\). Mỗi ô là ô trắng hoặc ô đen; trò chơi chỉ diễn ra trên các ô trắng. Mỗi người có một quân cờ, ban đầu đặt tại ô xuất phát của mình. Hai ô xuất phát đều trắng và khác nhau.

Trong mỗi lượt, người chơi di chuyển quân của mình sang một ô trắng kề cạnh theo một trong bốn hướng. Nếu quân vừa đi vào ô đang có quân đối phương, người chơi được đi thêm một bước; nhờ vậy quân có thể nhảy qua đối phương, và hướng của bước thứ hai không nhất thiết giống bước thứ nhất.

A đi trước, sau đó hai người luân phiên. Mục tiêu là đưa quân tới ô xuất phát của đối phương. Người đầu tiên làm được điều đó sẽ thắng. Hãy xác định người có chiến thuật thắng, tức có thể thắng bất kể đối phương đi như thế nào.

Trong hình trên, nếu A đi sang phải trong ba lượt đầu thì B sẽ đi lên trong ba lượt đầu. Ở lượt thứ ba, B đi vào ô của A, được đi thêm và sẽ tới ô xuất phát của A trước.

Trong hình trên, A có thể bắt đầu bằng một bước sang phải và một bước xuống dưới. Tùy hai bước đầu của B, A tiếp tục đi xuống hoặc sang phải để tránh B và tới ô xuất phát của B trước.

Dữ liệu vào

Dòng đầu chứa số nguyên \(t\) — số bộ test (\(1\le t\le 10\)).

Mỗi bộ test được mô tả như sau:

• Dòng đầu chứa số nguyên \(n\) (\(2\le n\le 300\)).
• \(n\) dòng tiếp theo, mỗi dòng gồm đúng \(n\) ký tự, mô tả bàn cờ. Mỗi ký tự là . (ô trắng), # (ô đen), A (ô xuất phát của A) hoặc B (ô xuất phát của B).

Luôn tồn tại một đường đi chỉ qua các ô trắng giữa hai ô xuất phát.

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa ký tự A hoặc B, cho biết người có chiến thuật thắng.

Phân nhóm

1. 40 điểm: \(n\le 40\).
2. 20 điểm: \(n\le 150\).
3. 40 điểm: không có ràng buộc bổ sung.

Ví dụ

2
4
A...
.#..
....
...B
4
A...
....
..#.
...B

B
A