問題文

長さ $N$ の A,B,C からなる文字列 $S$ のうち、以下の条件を満たすものの個数を $2$ で割ったあまり を求めてください。

• $S$ の $1$ 文字目から $i$ 文字目までからなる文字列を $S_i$ とする。$S_i$ に含まれる A,B,C の個数をそれぞれ $A_i,B_i,C_i$ とする。このとき、$1 \\le i \\le N$ を満たす任意の整数 $i$ に対し、以下が成り立つ。
  • $A_i-B_i \\le X$
  • $B_i-C_i \\le Y$
  • $C_i-A_i \\le Z$

この問題は、$T$ ケース与えられます。

制約

• $1 \\le T \\le 10$
• $1 \\le N \\le 10^9$
• $0 \\le X,Y,Z \\le 10^9$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$T$ $\\mathrm{case}_1$ $\\mathrm{case}_2$ $\\vdots$ $\\mathrm{case}_T$

各ケースは以下の形式で与えられる。

$N$ $X$ $Y$ $Z$

出力

各ケースについて、答えを出力せよ。

入力例 1

1
3 2 1 0

出力例 1

0

条件を満たす文字列は、AAB,AAC,ABA,ABC,ACA,ACB,BAA,BAC の $8$ 個があります。よって、解は $0$ です。

入力例 2

10
1 22 9 92
14 7 74 39
23 50 8 6
93 40 9 60
68 8 47 64
11 68 18 24
3 26 54 8
46 17 90 86
86 76 45 55
80 68 79 62

出力例 2

1
0
0
0
1
1
1
0
1
0