#2358. Brick Break Game

内存限制:128 MiB 时间限制:10 Sec

题目描述

     很久很久很久很久很久以前,有一个有趣的游戏。这个游戏是这样的,地上 有一些砖块,保证每一块的长度都是{1,2,3,4}的一个整数。每次你有两种操作, 拿走 n 个长度为 n 的砖块,或者把一个长度大于 1 的砖块分为两个长度大于等于 0 的砖块。如果某个玩家无法操作,就算这位玩家输。
现在给出你一些局面,判断这个游戏是先手必胜还是后手必胜。
 

输入格式

     输入的第一行包含一个整数 T,表示数据组数。
接下来有 T 组,每组四个整数 a b c d,表示长度为 1 2 3 4 的砖块分别有多少个。
 

输出格式

     输出 T 行,每行一个一个整数,1 表示先手必胜,0 表示后手必胜。
 

样例

样例输入


			
3 4210 0010 7010

样例输出


			
1 1 0

数据范围与提示

【数据说明】

30%数据满足:a+2b+3c+4d≤10

70%数据满足:max{a, b, c, d}≤14

100%数据满足:T≤10, max{a, b, c, d}≤10^10000