삼각형 전쟁

삼각형 전쟁은 아래 삼각형 격자 위에서 두 사람이 겨루는 게임이다.

점은 모두 10개이고, 위 줄부터 아래 줄로, 같은 줄에서는 왼쪽부터 오른쪽으로 1번부터 10번까지 번호가 붙어 있다. 첫 줄에 1번, 둘째 줄에 2번과 3번, 셋째 줄에 4번, 5번, 6번, 넷째 줄에 7번, 8번, 9번, 10번이 있다. 이웃한 두 점을 잇는 점선은 18개이고, 이 점선들이 격자를 작은 삼각형 9개로 나눈다.

A와 B가 번갈아 가며 아직 채우지 않은 점선을 하나씩 채우고, A가 먼저 시작한다. 한 번 채운 선은 다시 채울 수 없다. 방금 채운 선이 작은 삼각형을 하나 이상 완성하면 그 삼각형은 선을 채운 사람이 가져가고, 그 사람이 곧바로 한 번 더 채운다. 즉 상대는 한 차례를 건너뛴다.

예를 들어 아래 왼쪽 그림의 상황에서 A가 2번과 5번을 잇는 선을 채우면,

A라고 적힌 삼각형을 A가 가져가고, 한 번 더 두어 3번과 5번을 잇는 선을 채운다. 이제 B는 원한다면 2번과 3번, 5번과 6번, 6번과 9번을 차례로 이어 삼각형 3개를 가져갈 수 있다. 그러고 나서도 A에게 차례가 돌아가기 전에 한 번 더 둔다.

점선 18개를 모두 채우면 게임이 끝나고, 삼각형을 더 많이 가진 사람이 이긴다. 두 사람이 가진 삼각형 개수의 차이는 상관없다.

이미 둔 수 몇 개를 입력으로 받는다. 그 상황에서 두 사람이 모두 완벽하게 둔다고 할 때, 즉 각자 자신에게 가장 좋은 결과로 이어지는 수를 항상 고른다고 할 때 누가 이기는지 판정하라.

첫 줄에 게임의 개수를 나타내는 양의 정수가 주어진다.

각 게임의 첫 줄에는 그 게임에서 이미 둔 수의 개수 $m$ ($6 \le m \le 18$)이 주어진다. 이어지는 $m$개 줄에는 둔 순서대로 각 수가 i j 형태로 주어지며, 그 차례에 $i$번 점과 $j$번 점을 잇는 선을 채웠다는 뜻이다 ($i < j$). 주어지는 수는 모두 규칙에 맞다.

각 게임마다 게임 번호와 결과를 한 줄에 출력한다. $k$번째 게임에서 A가 이기면 Game k: A wins.를, B가 이기면 Game k: B wins.를 출력한다. 이때 k 자리에는 1부터 세는 실제 게임 번호를 쓴다.