题目描述

考虑长度为 $N$ 的字符串，由字符 A、B 和 C 构成。在这些字符串中，找出满足以下条件的字符串的数量，取模 $2$：

• 令 $S_i$ 为 $S$ 的前 $i$ 个字符构成的字符串。同时，令 $A_i$、$B_i$ 和 $C_i$ 分别表示 $S_i$ 中字符 A、B 和 C 的数量。对于所有满足 $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

满足条件的字符串有 $8$ 个：AAB,AAC,ABA,ABC,ACA,ACB,BAA,BAC。因此答案为 $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