Triangle Partitioning#1518
A triangle can be divided into two triangles by drawing a median to its largest side (in the figure, this division is shown with the red line). These two smaller triangles can then be divided in the same way into four triangles (shown in the figure with blue lines). This process of dividing triangles is continued infinitely.
Mathematicians have observed that during this process, only a finite number of "styles" of triangles are obtained, which differ only in size. Given the side lengths of the initial triangle, determine the number of distinct triangle styles that can be obtained. Two triangles are considered to be of the same style if they are similar.
The first line contains the number of tests (0 < n < 35). Each of the next lines contains three integers , , (0 < a, b, c < 100), which are the side lengths of the triangle. Every input triangle has positive area.
For each test, output in a separate line its serial number as shown in the example, followed by an integer — the number of distinct triangle styles obtained in the described process. You may assume that is always less than .
Beispiel 1