長方形in直角三角形

問題

$(0,0),(X,0),(X, Y)$の３点を結んでできる直角三角形があります。

この中に幅 $1$ 、高さ $H$ の長方形は何個敷き詰められますか？

ただし、長方形、三角形は回転させてはいけません。また、長方形の頂点は格子点になるようにしてください。

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

制約

• $1 \leqq T \leqq 10^5$
• $1 \leqq X,Y \leqq 10^9$
• $1 \leqq H \leqq 10^9$
• 入力は全て整数

入力

各テストケースは以下のように与えられます。

出力

$T$ 行出力してください。$i$行目には$\text{case}_i$の答えを出力してください。

入力例１

3
5 5 2
7 3 1
3 2 1

出力

4
6
1

以下のように敷き詰めれます。