Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BGAME - Game on board

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/bgame


{assign var="code" value="BGAME"} {if $par==""} {assign var=par value=$locale} {/if}
{if $par=="en"} {literal}

Two players, A and B, play a game on a square board of size n×n. The squares of the board are either white or black. The game is played only on the white squares — the black ones are excluded from the game. Each player has one piece, initially placed at this player’s starting point — one of the white squares on the board. The starting point of A is different than that of B.

In each move a player moves his piece to one of the neighboring white squares (either up, down, left or right). If the player moves his piece to the square currently occupied by his opponent’s piece, he gets an extra move (this way he jumps over the opponent). Note that in this case the direction of the second move can be different than that of the first move.

Player A moves first, then players alternate. The goal of the game is to reach the opponent’s starting point. The player whose piece reaches his opponent’s starting point first, wins the game. Even if the player’s last move consists of two jumps, and he only jumps over his opponent’s starting point (since it is occupied by his opponent), the player wins. We want to determine which player has a winning strategy (a player has a winning trategy if he can win regardless of his opponent’s moves).

Task

Write a program, that:

  • reads the layout of the grid and the starting points of the two players from the standard input,
  • finds the player who has a winning strategy,
  • writes the result to the standard output.

Input

The first line of the standard input contains one integer t the number of test cases (1 ≤ t ≤ 10 ). After it the description of t tests appears. Each test is described as follows. In the first line of the test there is one integer n (2 ≤ n ≤ 300 ), the length of the side of the grid. Then next n lines contain the description of the grid. Each line consists of n characters (with no whitespaces between them). Each character is either ’.’ a white square), ’#’ (a black square), ’A’ (the starting point of A) or ’B’ (the starting point of B).

You may assume that there exists a path of white squares between the starting points of A and B.

Output

For each test case exactly one line should be printed to standard output containing a single character ’A’ or ’B’, indicating the player who has a winning strategy.

Example

Input:
2
4
A...
.#..
....
...B
4
A...
....
..#.
...B


Output:
B
A

{/literal}{elseif ($par=="vn" || $par=="")}{literal}

Hai người chơi A và B chơi một trò chơi trên một bảng hình vuông kích thước n*n. Các ô vuông đơn vị của bảng có thể có màu trắng hoặc đen. Trò chơi chỉ được chơi trên các ô vuông màu trắng, không được động đến các ô màu đen. Mỗi người chơi có một quân cờ, ban đầu được đặt tại một ô gọi là ô xuất phát – một trong số các ô màu trắng của bảng. Ô xuất phát của A khác ô xuất phát của B.

Tại mỗi lượt đi, người chơi sẽ di chuyển quân cờ của mình sang một trong số các ô trắng hàng xóm của nó (có thể là phía trên, phía dưới, bên phải, hoặc bên trái). Nếu người chơi di chuyển quân cờ của mình đến ô vuông đang bị chiếm bởi quân cờ của đối phương thì anh ta sẽ được thêm một lượt đi tiếp. Chú ý rằng trong trường hợp này, hướng di chuyển ở lượt đi thứ hai có thể khác lượt đi trước đó.

Người chơi A đi trước, sau đó các người chơi luân phiên nhau thực hiện lượt đi. Mục tiêu của trò chơi là di chuyển quân cờ của mình đến được ô xuất phát của đối phương. Người chơi nào di chuyển quân cờ của mình đến ô xuất phát của đối thủ trước thì sẽ giành chiến thắng. Ngay cả khi ở lượt đi cuối cùng của người chơi chứa 2 bước di chuyển, và anh ta chỉ nhảy qua ô xuất phát của đối thủ (khi ô đó đang bị chiếm bởi quân cờ của đối phương), thì anh ta vẫn giành chiến thắng. Chúng ta muốn tính xem người chơi nào có chiến lược để giành chiến thắng (mà không cần quan tâm xem đối thủ của mình có chơi tốt đến đâu).

Task

Viết chương trình:

  • Đọc vào cách bố trí bảng ô vuông và các ô xuất phát của 2 người chơi từ standard input.
  • Tìm xem người nào sẽ có một chiến lược để giành thắng lợi.
  • Viết kết quả ra standard output

Input

Dòng đầu tiên của standard input chứa một số nguyên t là số lượng test ( 1 ≤ t ≤ 10). Sau đó sẽ là mô tả lần lượt của t test. Mỗi test được mô tả như sau: Trên dòng đầu tiên của bộ test là số nguyên n ( 2 ≤ n ≤ 300), là độ dài của bảng ô vuông. N dòng tiếp theo chứa thông tin về bảng ô vuông. Mỗi dòng chứa n kí tự (không có dấu cách ở giữa). Mỗi kí tự có thể là ‘.’ (ô màu trắng), ‘#’ (ô màu đen), ‘A’ (ô xuất phát của A), hoặc ‘B’ (ô xuất phát của B).

Bạn có thể chắc chắn rằng sẽ tồn tại một đường đi gồm các ô trắng giữa điểm xuất phát của A và điểm xuất phát của B.

Output

Với mỗi test, in ra trên đúng 1 dòng của standard output một kí tự ‘A’ hoặc ‘B’ chỉ ra người nào sẽ có chiến lược giành chiến thắng.

Example

Input:
2
4
A...
.#..
....
...B
4
A...
....
..#.
...B


Output:
B
A

{/literal} {/if}

Được gửi lên bởi:Race with time
Ngày:2008-12-14
Thời gian chạy:1s-26s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:BOI

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.