Triangle War

Triangle War is a two-player game played on the following triangular grid:

Two players, A and B, take turns filling in any dotted line connecting two dots, with A going first. Once a line is filled, it cannot be filled again. If the line a player fills completes one or more triangles, that player owns those triangles and takes another turn (the opponent's turn is skipped). The game ends once all dotted lines are filled, and the player who owns the most triangles wins. The size of the margin does not matter.

For example, suppose A fills in the line between 2 and 5 in the partial game on the left below:

Then A owns the triangle labelled A and takes another turn, filling in the line between 3 and 5. B can now claim 3 triangles (if desired) by filling in the line between 2 and 3, then the line between 5 and 6, and finally the line between 6 and 9; B would then take one more move before it becomes A's turn again.

In this problem you are given a number of moves that have already been made. From the partial game, determine which player wins, assuming both players play perfectly from that point on — that is, each player always chooses the move that leads to the best possible outcome for themselves.

The first line of input is a positive integer, the number of games that follow. Each game begins with an integer $m$ ($6 \le m \le 18$), the number of moves already made in that game. The next $m$ lines each describe a move in order, in the form i j (with $i < j$), meaning the line between dots $i$ and $j$ is filled on that move. You may assume every given move is legal.

For each game, print one line: Game k: A wins. if A wins, or Game k: B wins. if B wins, where k is the game's number (the first game is 1).