F - Fifty-Fifty? Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

うさぎは，A を A 個，B を B 個持っている．うさぎはこれらから N 文字を選んで並べて作ることの出来る K 次回文の個数の偶奇が気になっている．

ただし，K 次回文とは，以下のような操作をちょうど K 回行うことで回文にすることの出来る文字列のことを指すものとする．

  • 追加：文字列の末尾に文字を 1 つ追加する．
  • 削除：文字列の末尾の文字を 1 つ削除する．
  • 置換：文字列の末尾の文字を 1 つ，別の文字に置き換える．

例えば ABB は，追加を 1 回行うことで ABBA に出来るため，1 次回文である．また，削除を 1 回行ってから置換を 1 回行うことで AA に出来るため，2 次回文でもある．

この問題では 1 つの入力データに複数のテストケースが含まれている．テストケースの個数は T 個であり，i\ (1 \leq i \leq T) 番目のテストケースでは N_i,\ A_i,\ B_i,\ K_i の組が与えられる．

制約

  • 1 \leq T \leq 100．
  • 0 \leq A_i,\ B_i \leq 100．
  • 1 \leq N_i \leq A_i+B_i．
  • 0 \leq K_i \leq N_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 行ずつ出力せよ．

入力例 1

2
3 3 1 0
3 1 2 2

出力例 1

0
1

1 つ目のテストケースで作ることの出来る 0 次回文は AAA と ABA の 2 つである．0 次回文は回文そのものである点に注意せよ．

2 つ目のテストケースで作ることの出来る 2 次回文は ABB と BAB と BBA の 3 つである．