{"raw_statement":[{"iden":"problem statement","content":"Consider strings of length $N$ consisting of `A`, `B`, and `C`. Among them, find the number of strings that satisfy the following condition, modulo $2$:\n\n*   Let $S_i$ be the string formed by the first $i$ characters of $S$. Also let $A_i$, $B_i$, and $C_i$ be the numbers of `A`'s, `B`'s, and `C`'s in $S_i$, respectively. For all $i$ such that $1 \\le i \\le N$, the following holds:\n    *   $A_i-B_i \\le X$\n    *   $B_i-C_i \\le Y$\n    *   $C_i-A_i \\le Z$\n\nYou have $T$ test cases to solve."},{"iden":"constraints","content":"*   $1 \\le T \\le 10$\n*   $1 \\le N \\le 10^9$\n*   $0 \\le X,Y,Z \\le 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is in the following format:\n\n$N$ $X$ $Y$ $Z$"},{"iden":"sample input 1","content":"1\n3 2 1 0"},{"iden":"sample output 1","content":"0\n\n$8$ strings satisfy the condition: `AAB`,`AAC`,`ABA`,`ABC`,`ACA`,`ACB`,`BAA`,`BAC`. Therefore the answer is $0$."},{"iden":"sample input 2","content":"10\n1 22 9 92\n14 7 74 39\n23 50 8 6\n93 40 9 60\n68 8 47 64\n11 68 18 24\n3 26 54 8\n46 17 90 86\n86 76 45 55\n80 68 79 62"},{"iden":"sample output 2","content":"1\n0\n0\n0\n1\n1\n1\n0\n1\n0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}