問題文

以下のような根付き木があります。

• 根に $A$ 個の子がついている。
• 根の $A$ 個の子にそれぞれ $B$ 個ずつ葉がついている。

例えば、$A=3,\ B=2$ の場合は下図のような根付き木となります。

そして、例えば下図の $3$ つの塗り方は全て同じと見なされます。

入力

$T$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$:$
$A_T$ $B_T$ $C_T$

• $T\ (1 \leq T \leq 10^5)$ はテストケース数を表す。
• $A_i,B_i,C_i\ (1 \leq A_i,B_i,C_i \leq 10^6)$ は問題文中で示した通りの値である。

出力

各テストケースに対する答えを $1$ 行ずつ出力してください。 最後に改行してください。

サンプル

4
2 2 2
1 1 999999
1000000 1000000 1
31415 9265 35897

0
1
1
0