Alice and Bob want to play a game. The game is played on a chessboard with \textbf{R} rows and \textbf{C} columns, for a total of \textbf{R}×\textbf{C} squares. Some of these squares are burned. A king will be placed on an unburned square of the board, and Alice and Bob will make successive moves with the king. In a move, the player must move the king to any of its \textbf{8} neighboring squares, with the following two conditions: \begin{itemize} \item The destination square must not be burned. \item The king must never have been in the destination square before. \end{itemize} If a player can’t make a move, he or she loses the game. Alice will move first; you need to determine who will win, assuming both players play optimally. \InputFile The first line of input gives the number of cases, \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}). \textbf{N} test cases follow. The first line of each case will contain two integers, \textbf{R} and \textbf{C} (\textbf{1} ≤ \textbf{R}, \textbf{C} ≤ \textbf{15}). The next \textbf{R} lines will contain strings of length \textbf{C}, representing the \textbf{C} squares of each row. Each string will contain only the characters '\textbf{.}', '\textbf{#}' and '\textbf{K}': \begin{itemize} \item '\textbf{#}' means the square is burned; \item '\textbf{.}' means the square is unburned, and unoccupied; and \item '\textbf{K}' means the king is in that cell at the beginning of the game. \end{itemize} There will be exactly one '\textbf{K}' character in each test case. \OutputFile For each test case, output one line containing "\textbf{Case #X: }" (where \textbf{X} is the case number, starting from \textbf{1}) followed by \textbf{A} if Alice wins, or \textbf{B} if Bob wins.