AT_xmascon16_f Fifty-Fifty?

[problemUrl]: https://atcoder.jp/contests/xmascon16noon/tasks/xmascon16_f うさぎは，`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 $ の組が与えられる．

入力は以下の形式で標準入力から与えられる． > $ 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\ \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 $． ### Sample Explanation 1 $ 1 $ つ目のテストケースで作ることの出来る $ 0 $ 次回文は `AAA` と `ABA` の $ 2 $ つである．$ 0 $ 次回文は回文そのものである点に注意せよ． $ 2 $ つ目のテストケースで作ることの出来る $ 2 $ 次回文は `ABB` と `BAB` と `BBA` の $ 3 $ つである．