長方形in直角三角形

2 secs 1024 MB
shinnshinn's icon shinnshinn

問題

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

この中に幅 11 、高さ HH の長方形は何個敷き詰められますか?

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

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

制約

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

入力

TT
case1\text{case}_1
\vdots
caseT\text{case}_T

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

X  Y  HX \; Y \; H

出力

TT 行出力してください。ii行目にはcasei\text{case}_iの答えを出力してください。

入力例1

3
5 5 2
7 3 1
3 2 1

出力

4
6
1

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

Submit


Go (1.21)