NEFU OJ Problem1356 帽儿山奇怪的棋盘 题解

帽儿山奇怪的棋盘

题目：

Time Limit:1000ms | Memory Limit:65535K

Description

军哥来到了帽儿山，发现有两位神人在顶上对弈。棋盘长成下图的模样：

每个点都有一个编号：由上到下，由左到右，依次编号为 1、2……12。两位神人轮流博弈，每一轮操作的一方可以取走一个棋子，或者取走相邻的两个棋子（即在同一直线上相邻的棋子）。取走最后一颗棋子的人输。给定初始状态，如果两个人都采取最优决策，问谁能赢。

Input

第一行一个数 n 表示数据组数，接下来 n 行每行一个长度为 12 的 01 串，1 表示该位置上有棋子，0 表示没有。(n<=100)

Output

输出一行，一个长度为 n 的 01 串，0 表示先手赢，1 表示后手赢。

Sample Input

3
110000000000
100000000000
110000000011

Sample Output

010

思路：