Upwinder最近喜欢上了一款古老的起源于Scandinavia(斯堪迪纳维亚半岛)的小游戏。具体的游戏规则如下：
棋盘的大小为8行8列，有两个玩家：狐狸和小狗。初始的时候有4只小狗被放置在棋盘最上边一行的4个黑色格子里；而1只狐狸被放在最下边一行的某个黑色格子里。以棋盘左上角为原点，向下为行的正方向，向右为列的正方向，从1开始给每一个格子编号.
(1) 两个玩家轮流下棋。
(2) 狐狸每轮可以斜着向上或斜着向下移动至相邻的一个空格子，只能移动一步；
(3) 小狗每轮只能斜着向下移动至相邻的一个空格子，只能移动一只，且只能移动一步；
(4) 显然根据移动规则棋盘中只有黑色的格子才能放棋子
狐狸与小狗的目标是不同的。
(1) 如果小狗将狐狸围住致使其无法移动(包括围在边界)，那么小狗获胜。
(2) 如果狐狸到达了棋盘最上方一行的任意一个黑色格子，那么狐狸获胜；
特别的，游戏不存在平局或死局，而且如果4只小狗均无法移动，则狐狸可以一直移动直至取胜。
现在告诉你游戏过程中的某一个局面，你能帮Upwinder判断如果狐狸与小狗均采取最优策略的话，谁能取得最后的胜利吗？
第一行一个数字T表示接下来有T(T<=3000)种局面。
对于每一种局面，由三行数据组成，其中：
第一行为整数0或1。0代表当前狐狸掌握棋权，1代表当前小狗掌握棋权。
第二行为两个整数，以空格分隔，依次是狐狸在棋盘上的行坐标Fr和列坐标Fl。
第三行为八个整数，以空格分隔，依次是第一只小狗的行坐标Dr1,列坐标Dl1……以此类推。
对于每一种局面，仅输出一行。
如果狐狸能够取胜，请输出“Fox win”(不含引号)
如果小狗能够取胜，请输出“Dog win”(不含引号)
#include <stdio.h>
typedef struct{
int x;
int y;
}P;
int chess(int s, P *f, P *d){
int i,j;
if(f->x < 1 || f->x > 8 || f->y < 1 || f->y > 8){
return -1;
}
for(i=0; i<4; i++){
if(d[i].x < 1 || d[i].x > 8 || d[i].y < 1 || d[i].y > 8){
return -1;
}
if(d[i].x == f->x && d[i].y == f->y){
return -1;
}
for(j=0;j<4;j++){
if(i != j && d[j].x == d[i].x && d[j].y == d[i].y){
return -1;
}
}
}
for(i=0;i<4;i++){
if(f->y > d[i].y){
break;
}
}
if(i==4){
return 0;
}
if(s==0){
f->x--; f->y--;
i = chess(1, f, d); if(i>=0) return i;
f->x; f->y+=2;
i = chess(1, f, d); if(i>=0) return i;
f->x+=2; f->y;
i = chess(1, f, d); if(i>=0) return i;
f->x; f->y-=2;
i = chess(1, f, d); if(i>=0) return i;
f->x--; f->y++;
//fox cannot move to any other point, game over.
if(f->y == 1){
return 0;
}else{
return 1;
}
}else{
for(j=0; j<4; j++){
d[j].x++; d[j].y++;
i = chess(0, f, d); if(i>0) return i;
d[j].x-=2; d[j].y;
i = chess(0, f, d); if(i>0) return i;
d[j].x++; d[j].y--;
}
//dog cannot move to any other point, fox is the leader.
return chess(0, f, d);
}
}
void main(){
int t,s,ret;
P f,d[4];
scanf(" %d", &t);
while(t--){
scanf(" %d", &s);
scanf(" %d %d", &f.x, &f.y);
scanf(" %d %d %d %d %d %d %d %d", &d[0].x, &d[0].y, &d[1].x, &d[1].y, &d[2].x, &d[2].y, &d[3].x, &d[3].y);
ret = chess(s, &f, d);
if(ret == 0){
printf("Fox win\n");
}else{
printf("Dog win\n");
}
}
}