Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB
配点 : 100 点
うさぎは，A を A 個，B を B 個持っている．うさぎはこれらから N 文字を選んで並べて作ることの出来る K 次回文の個数の偶奇が気になっている．
ただし，K 次回文とは，以下のような操作をちょうど K 回行うことで回文にすることの出来る文字列のことを指すものとする．
例えば ABB は，追加を 1 回行うことで ABBA に出来るため，1 次回文である．また，削除を 1 回行ってから置換を 1 回行うことで AA に出来るため，2 次回文でもある．
この問題では 1 つの入力データに複数のテストケースが含まれている．テストケースの個数は T 個であり，i\ (1 \leq i \leq T) 番目のテストケースでは N_i,\ A_i,\ B_i,\ K_i の組が与えられる．
入力は以下の形式で標準入力から与えられる．
T N_1 A_1 B_1 K_1 N_2 A_2 B_2 K_2 : N_T A_T B_T K_T
それぞれのテストケースに対し，作ることの出来る K 次回文の個数を 2 で割った余りを 1 行ずつ出力せよ．
2 3 3 1 0 3 1 2 2
0 1
1 つ目のテストケースで作ることの出来る 0 次回文は AAA と ABA の 2 つである．0 次回文は回文そのものである点に注意せよ．
2 つ目のテストケースで作ることの出来る 2 次回文は ABB と BAB と BBA の 3 つである．