Алиса и Боб играют в игру. Игра ведётся на доске, состоящей из \textbf{R} строк и \textbf{C} столбцов, в общей сложности из \textbf{R}×\textbf{C} клеток. Некоторые из этих клеток сожжены. Король размещен в одной из несгоревших клеток, а Алиса и Боб делают поочерёдно ходы королём. За один ход игрок должен переместить короля в любую из его \textbf{8} соседних клеток, соблюдая при этом следующие два условия: \begin{itemize} \item Клетка назначения не должна быть сожжена. \item Король никогда не должен быть перемещён в клетку, в которой уже побывал до этого. \end{itemize} Если игрок не может сделать ход, он или она проигрывает. Первой ход делает Алиса, а вы должны определить, кто победит, предполагая, что оба игрока играют оптимально. \InputFile В первой строке входа задано количество последующих тестовых примеров \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}). Далее идут сами \textbf{N} тестовых примеров. Первая строка в каждом тестовом случае будет состоять из двух целых чисел, \textbf{R }и \textbf{C }(\textbf{1} ≤ \textbf{R} , \textbf{C} ≤ \textbf{15} ). Следующие \textbf{R} строк будут содержать строки длиной \textbf{C}, представляющих \textbf{C} клеток каждой строки. Каждая строка будет содержать только символы "\textbf{.}", "\textbf{#}" и "\textbf{K}": \begin{itemize} \item "\textbf{#}"обозначает сожжённую клетку; \item "\textbf{.}" обозначает, что клетка не сгорела и не занята; \item "\textbf{K}"обозначает клетку, в которой находится король в начале игры. \end{itemize} Гарантируется, что будет только одна клетка, содержащая "\textbf{К}" в каждом из тестов. \OutputFile Для каждого теста выведите одну строку, содержащую "\textbf{Case # X:} "(где \textbf{X} это номер теста, начиная с \textbf{1} ), а затем \textbf{A}, если победит Алиса, или \textbf{B}, если выигрывает Боб.