2.砖块游戏

题目描述

地上有一些砖块，每一块的长度都为$1$，$2$，$3$，$4$中的一个整数。两名玩家轮流进行操作，操作共有两种：

1. 取走$n$个长度为$n$的砖块（$1 \leq n \leq 4$）；
2. 选择一个长度为$n$的砖块（$n \geq 2$），将其分解为两个长度分别为$m$，$n-m$的砖块（$0 < m < n$）。

如果一个玩家无法进行任何操作，则他的对手赢得游戏。

给定$T$局游戏的初始局面，你需要求出每局游戏先手是否必胜。

输入格式

第一行一个整数$T$，表示游戏的次数。

接下来$T$行，每行四个整数$a$，$b$，$c$，$d$，分别表示长度为$1$，$2$，$3$，$4$的砖块的数量。

输出格式

对于每组数据输出一行，如果先手必胜输出$1$，否则输出$0$。

数据范围与提示

• 对于$30\%$的数据，$a+2b+3c+4d \leq 10$；
• 对于$50\%$的数据，$\max\{a,b,c,d\} \leq 14$；
• 对于$100\%$的数据，$1 < T < 10$，$\max\{a,b,c,d\} \leq 10^{10000}$。

样例

3
4 2 1 0
0 0 1 0
7 0 1 0

1
1
0