1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;

int tra[10],bin[20],dot[11][11];

void init()
{
    dot[1][2]=1;dot[1][3]=2;dot[2][3]=3;dot[2][4]=4;dot[2][5]=5;dot[3][5]=6;dot[3][6]=7;dot[4][5]=8;dot[5][6]=9;
    dot[4][7]=10;dot[4][8]=11;dot[5][8]=12;dot[5][9]=13;dot[6][9]=14;dot[6][10]=15;dot[7][8]=16;dot[8][9]=17;dot[9][10]=18;
    tra[1]=7;tra[2]=152;tra[3]=52;tra[4]=352;tra[5]=34304;tra[6]=3200;tra[7]=71680;tra[8]=12544;tra[9]=155648;
}

int check(int x,int y)
{
    int ans=0;
    for (int i=1;i<=9;i++)
        if ((x&tra[i])==tra[i]&&(bin[y]&tra[i])==bin[y]) ans++;
    return ans;
}

int findmin(int now,int beta,int ca,int cb);
int findmax(int now,int alpha,int ca,int cb)
{
    if (now==bin[18]-1) return ca>cb?1:-1;
    if (ca>=5) return 1;
    if (cb>=5) return -1;
    int ans=-1;
    for (int i=1;i<=18;i++)
        if ((now&bin[i-1])==0)
        {
            int x=now+bin[i-1];
            int w=check(x,i-1);
            if (w) ans=max(ans,findmax(x,alpha,ca+w,cb));
            else ans=max(ans,findmin(x,ans,ca,cb));
            if (ans>=alpha) return ans;
        }
    return ans;
}

int findmin(int now,int beta,int ca,int cb)
{
    if (now==bin[18]-1) return ca>cb?1:-1;
    if (ca>=5) return 1;
    if (cb>=5) return -1;
    int ans=1;
    for (int i=1;i<=18;i++)
        if ((now&bin[i-1])==0)
        {
            int x=now+bin[i-1];
            int w=check(x,i-1);
            if (w) ans=min(ans,findmin(x,beta,ca,cb+w));
            else ans=min(ans,findmax(x,ans,ca,cb));
            if (ans<=beta) return ans;
        }
    return ans;
}

int main()
{
    bin[0]=1;
    for (int i=1;i<=18;i++)
        bin[i]=bin[i-1]*2;
    init();
    int t;
    scanf("%d",&t);
    for (int l=1;l<=t;l++)
    {
        int n;
        scanf("%d",&n);
        int s=0,next=0,ca=0,cb=0;
        for (int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if (x>y) swap(x,y);
            s+=bin[dot[x][y]-1];
            int w=check(s,dot[x][y]-1);
            if (w)
            {
                if (!next) ca+=w;
                else cb+=w;
            }
            else next^=1;
        }
        int tmp;
        if (!next) tmp=findmax(s,1,ca,cb);
        else tmp=findmin(s,-1,ca,cb);
        if (tmp>0) printf("Game %d: A wins.n",l);
        else printf("Game %d: B wins.n",l);
    }
    return 0;
}