squares
What is the maximal number of squares with side lengths of K
that can be packed - without overlaps - into a right triangle whose legs are of lengths A
and B
? For each square one of its side must be parallel with one of the triangles leg!
Example
In the figure above one can see the solution (M=6
) in the case of K=2,A=7,B=12
.
Input Specification
T
K1 A1 B1
...
KT AT BT
The first line is the number cases to be solved. Then T
lines follow, each of which with three space separated numbers Ki,Ai,Bi
.
1 ≤ T ≤ 100
1 ≤ Ki ≤ 100
1 ≤ Ai,Bi ≤ 104 (i=1...T)
Output Specification
M1
...
MT
T
lines with the required values of Mi (i=1...T)
.
Sample Input 1
1
2 7 12
download as text file
Sample Output 1
6
download as text file
Sample Input 2
4
2 10 10
2 3 3
17 1717 17171
71 7171 71717
download as text file
Sample Output 2
10
0
50500
50500
download as text file