Combination Locks
Description
Alice and Bob are playing with combination locks. Each of them has a combination lock that consists of $N$ rotating discs with digits 0 to 9 engraved on them. Their friend Charlie doesn't have a lock and has devised a game to keep them occupied. He will keep track of whether the corresponding digits of their locks match and will describe the current situation with a difference pattern string $S$. The $j$-th character of $S$ is either "=" or "." and indicates whether the $j$-th digits in Alice's and Bob's locks match or not, respectively.
Charlie will officiate the game, while Alice and Bob take turns with Alice starting first. On each move, a player has to change one digit of their combination lock. As Charlie only keeps track of the difference patterns, this pattern has to change for a move to be valid. He is also rather superstitious and has brought a list of patterns $P_i$ that must not appear during the game. Charlie's main task is to enforce the rule that no difference pattern repeats during the course of the game. The player who can't make a move loses the game.
Write a program that will determine the winner of the game if both players play optimally.
The first line contains the number of test cases $T$. Each test case starts with a line containing two space-separated integers $N$ and $C$. This is followed by two lines that describe the starting configuration of Alice's and Bob's combination lock. A lock configuration is a string of $N$ digits. The following $C$ lines describe Charlie's superstitious patterns $P_i$. The superstitious list doesn't contain duplicates and it is guaranteed that the difference pattern of the starting lock configurations is not on the superstitious list.
Input limits
- $1 \leq T \leq 20$
- $1 \leq N \leq 10$
- $0 \leq C \leq 1000$
For every test case output one line with the name of the winner.
Input
The first line contains the number of test cases $T$. Each test case starts with a line containing two space-separated integers $N$ and $C$. This is followed by two lines that describe the starting configuration of Alice's and Bob's combination lock. A lock configuration is a string of $N$ digits. The following $C$ lines describe Charlie's superstitious patterns $P_i$. The superstitious list doesn't contain duplicates and it is guaranteed that the difference pattern of the starting lock configurations is not on the superstitious list.
Input limits
- $1 \leq T \leq 20$
- $1 \leq N \leq 10$
- $0 \leq C \leq 1000$
Output
For every test case output one line with the name of the winner.
3
2 2
12
89
=.
==
3 1
204
101
.==
3 2
000
000
...
==.
Alice
Bob
Bob
Note
In the first example, the only move for Alice is to change the second digit from $2$ to $9$. Any other move is invalid because it doesn't change the difference pattern or because it would result in a superstitious pattern. Bob doesn't have a valid move, therefore Alice wins.