問題文

非負整数 $A,B,D$ が与えられます。$⊕$ を、排他的論理和を表す記号とします。

• $B$ $⊕$ $C = A$
• $C$ $⊕$ $A = B$

を両方満たす非負整数 $C$ は、$D$ 以下の非負整数で、いくつあるでしょうか？

$T$ 個 のテストケースが与えられるので、それぞれについて答えてください。

制約

$1 ≤ T ≤ 5*10^5$
$0 ≤ A,B,D ≤ 10^{18}$

入力

入力は $T$ 行からなる。 $1$ 行目に $T$ が与えられ、$2$ 行目から $T+1$ 行目にかけて、非負整数 $A,B,D$ が与えられる。

出力

$T$ 行出力してください。

入力例 1

1
0 0 0

出力例 1

1

条件を満たす非負整数 $C$ は、 $C=0$ の $1$ つのみです。