配点 : $1100$ 点

問題文

長さ $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$
• $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
3 2 1 0

0

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

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

1
0
0
0
1
1
1
0
1
0