Reveal All Red Cells

You are given q boards of size \(5\times5\)</em> where each cell is assigned one of four colors: red (r), blue (b), neutral (n) and a special color (x). In every board the distribution of the colors among the hidden cells is fixed: exactly 9 red, 8 blue, 5 neutral and 1 special cell. (Note: some boards may have some cells already revealed.)

The board has a fixed mapping for positions. The cell at row \(i\) and column \(j\) always corresponds to the \(\textbf{letter}\) in the following order:

abcde
fghij
klmno
pqrst
uvwxy

If a cell is revealed, its corresponding color letter is shown in uppercase; otherwise it is shown in lowercase. For example, an unrevealed red cell is represented by r while a revealed red cell is represented by R.

You are also given a list of n candidate strings \(w\), each being a permutation of the 25 letters abcdefghijklmnopqrstuvwxyz. You must select one candidate \(w\) and a positive integer \(g\) (the number of operations) so that by performing the procedure below, you will end up with all red cells revealed.

The procedure is as follows. You start with an index \(i=1\) (that is, the first character in \(w\)). Then you perform up to \(g\) operations (or stop earlier if all red cells have been revealed):

1. If the cell corresponding to \(w_i\) is already revealed, do nothing and set \(i \gets i+1\).
2. If it is not revealed, flip (reveal) that cell. If the flipped cell’s color (its lowercase letter) is not r (i.e. if it is n, b or x), you lose.
3. Then, set \(i \gets i+1\) and continue.

The process stops when either you have performed \(g\) operations or when all red cells have been revealed. Your task is to select a candidate string \(w\) from the given list and an integer \(g\) so that the procedure ends with all red cells revealed (and you never reveal a non-red cell).

inputFormat

The first line contains an integer \(t\) (\(1 \le t \le 100\)) indicating the number of test cases. Each test case is described as follows:

1. 5 lines, each containing a string of 5 characters representing the board. Each character is one of r, b, n, x if hidden, or their uppercase versions if already revealed.
2. An integer \(n\) (the number of candidate strings).
3. \(n\) lines follow, each containing a candidate string which is a permutation of abcdefghijklmnopqrstuvwxyz (i.e. exactly 25 lowercase letters).

The fixed mapping of board positions is as follows:

abcde
fghij
klmno
pqrst
uvwxy

outputFormat

For each test case, print the chosen candidate string \(w\) and the integer \(g\) (the number of operations performed) separated by a space. It is guaranteed that at least one candidate exists that will reveal all red cells safely.

sample

1
Rbdde
fghij
klmno
pqrst
uvwxy
3
acfhkmprwbdgijlnoqstuvxey
abcdefghijklmnopqrstuvwxyz
wxyacfhkmprbdgijlnoqstuv

acfhkmprwbdgijlnoqstuvxey 9