Description
很久很久很久很久很久以前,有一个有趣的游戏。这个游戏是这样的,地上 有一些砖块,保证每一块的长度都是{1,2,3,4}的一个整数。每次你有两种操作, 拿走 n 个长度为 n 的砖块,或者把一个长度大于 1 的砖块分为两个长度大于等于 0 的砖块。如果某个玩家无法操作,就算这位玩家输。
现在给出你一些局面,判断这个游戏是先手必胜还是后手必胜。
Input
输入的第一行包含一个整数 T,表示数据组数。
接下来有 T 组,每组四个整数 a b c d,表示长度为 1 2 3 4 的砖块分别有多少个。
Output
输出 T 行,每行一个一个整数,1 表示先手必胜,0 表示后手必胜。
Sample Input
3 4210 0010 7010Sample Output
1 1 0Hint
【数据说明】
30%数据满足:a+2b+3c+4d≤10
70%数据满足:max{a, b, c, d}≤14
100%数据满足:T≤10, max{a, b, c, d}≤10^10000
