初看题目木有什么思路，后来仔细看了下发现m>=6，这个是一个很关键的点。意味着我们需要求解的未放火柴只有12根，2^12 = 4096，这12根放与未放的情形只有4000多种，故可以采用状态DP。。。记忆化搜索一下。。详细见代码。
//By Lin
#include<cstdio>
#include<cstring>

using	 namespace std; 
int	m,mark[19],last[15],dp[5000][3];
const int	triangle[19][5]  = {{0,0,0,0,0},{1,2,3,0,0},{1,1,3,0,0},{2,1,2,5,7},{1,5,6,0,0},{2,4,6,3,7},{2,4,5,11,13},
														  {2,3,5,8,9},{1,7,9,0,0},{2,7,8,14,16},{1,11,12,0,0},{2,10,12,6,13},{1,10,11,0,0},
														  {2,6,11,14,15},{2,13,15,9,16},{1,13,14,0,0},{2,9,14,17,18},{1,16,18,0,0},{1,16,17,0,0}}; 

void	swap(int &x ,int &y ) 
{
		int	temp = x; 
		x = y; 
		y = temp; 
}

int	jisuan(int x , int y ) 
{
		if ( x>y ) swap(x ,y ); 
		if ( y == x+1 && x != 1 )
		{
				if ( x >=7 ) x -= 3; 
				else if ( x>=4 ) x-=2; 
				else x-=1; 
				return x*3; 
		}
		int	t = x; 
		if ( x >= 4 ) t+=3; 
		else if ( x>=2 ) t+=2; 
		else t+=1;
		int	ret = (x-1)*3;
		ret +=  y>t?2:1;
		return ret; 
}

void	solve(int &x ,int &y ,int now ,int e ) 
{
		if ( e == 0 ) { x = 0; y = 0; return;}
		if ( dp[e][2] == 1 ) 
		{
				x = dp[e][now]; 
				y = dp[e][(now+1)%2]; 
				return;
		}

		int	 k = 1,s[2]; 
		dp[e][0] =-1; 
		for (int o = 0; o<18-m; o++ , k *= 2 )
		{
				if ( (k&e) == 0 ) continue;
				s[0] = s[1] = 0; 
				int	 i = last[o]; 
				mark[i] = 1; 
				bool f = false;
				for (int j = 1; j<=triangle[i][0]; j++ ) 
						if ( mark[triangle[i][j*2]] == 1 && mark[ triangle[i][j*2-1] ] == 1 ) 
						{
								f = true; 
								s[0]++; 
						}
				int	p ,q ; 
				solve( p , q , f?0:1 , e ^ k );
				s[0] += p; s[1] = q; 
				if ( s[0] > dp[e][0]  ) { dp[e][0] = s[0]; dp[e][1] = s[1]; }		
				mark[i] = 0;
		}

		dp[e][2] = 1; 		
		x = dp[e][now]; 
		y = dp[e][(now+1)%2]; 

		return;
}

int	main()
{
		int	cas,tt = 1;  
		scanf("%d" , &cas ); 
		while ( cas-- )
		{
				int	x, y,s[2],now,k; 
				scanf("%d" , &m ); 
				now = s[0] = s[1] = 0;
				memset( mark , 0 , sizeof(mark) ) ; 
				for (int i = 0; i<m; i++ ) 
				{
						scanf("%d%d" , &x,&y );
						k = jisuan(x ,y ); 
						bool f = false;
						for (int j = 1; j<=triangle[k][0]; j++ ) 
								if ( mark[triangle[k][j*2]] == 1 && mark[ triangle[k][j*2-1] ] == 1 ) 
								{
										f = true; 
										s[now]++; 
								}
						mark[k] = 1; 
						if ( !f )  now = (now+1)%2; 
				}
				k = 0; 
				int e = 0; 
				for (int i = 1; i<=18; i++) 
						if ( mark[i] == 0 ) { last[k++] = i;  e = e*2 + 1; }
				memset( dp, 0 , sizeof(dp) ); 
				solve( x , y , now , e ); 
				s[0] += x; 
				s[1] += y;

				printf("Game %d: " , tt++ ); 
				if ( s[0] > s[1] ) printf("A wins.\n"); 
				else printf("B wins.\n"); 
		}
		return 0; 
}