题目描述

很久很久很久很久很久以前，有一个有趣的游戏。这个游戏是这样的，地上有一些砖块，保证每一块的长度都是 ${1,2,3,4}$ 的一个整数。每次你有两种操作，拿走 $n$ 个长度为 $n$ 的砖块，或者把一个长度大于 $1$ 的砖块分为两个长度大于 $0$ 的砖块。如果某个玩家无法操作，就算这位玩家输。

现在给出一些局面，判断这个游戏是先手必胜还是后手必胜。

输入格式

输入的第一行包含一个整数 $T$,表示数据组数。

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

输出格式

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

样例输入

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

样例输出

1
1
0

数据规模与约定

$30\%$ 数据满足：$a+2b+3c+4d\le 10$。

$70\%$ 数据满足：$\max(a, b, c, d)\le 14$。

$100\%$ 数据满足：$T\le 10$，$\max(a, b, c, d)\le 10^{10000}$。