TRIPART - Triangle Partitioning

no tags 

A triangle can be divided into two equal triangles by drawing a median on its largest edge (in the figure below such a division is shown with the red line). Then the smaller two triangles can be divided in similar fashion into equal triangles (shown in the picture below with blue lines). This process can continue forever.

Some mathematicians have found that when we split a triangle into smaller ones using the method specified above we have only some "styles" of triangles that only differ in size. So now given the lengths of the sides of the triangle your job is to find out how many different styles of small triangles we have. (Two triangles are of same style if they are similar.)

Input

First line of the input file contains an integer N (0 < N < 35) that indicates how many lines of input there are.

Each line contains three integers a, b, c (0 < a,b,c < 100) which indicate the sides of a valid triangle. (A valid triangle means a real triangle with positive area.)

Output

For each line of input you should produce an integer T, which indicates the number of different styles of small triangles, formed for the triangle at input. Look at the example for details. You can safely assume that for any triangle T will be less than 100.

Example

Input:
2
3 4 5
12 84 90

Output:
3
41

hide comments
Smithers: 2012-11-03 23:58:53

pardeep kumar, Charizard_: The problem states "Two triangles are of same style if they are similar." For the definition of similar, see http://en.wikipedia.org/wiki/Similarity_%28geometry%29#Similar_triangles

Bonus chatter: Just revisited this problem after I got a WA 3 years ago. Turns out I'd just forgotten to take out the code that prints all of the types of triangles before the answer.

Charizard_: 2012-09-15 11:17:02

Please explain the test cases....what is "styles" of triangle???

pardeep kumar: 2012-06-13 10:02:31

can anybody explain the output of the
above examples ...i am not getting it.according to me there are only following styles of the triangles...
1.right angled
2.isosceles
3.equilateral
4.scalene
so for each input there should be only maximum 4 styles of the triangles...please explain it...so how the output is 41 for the second example.

Last edit: 2012-06-13 10:03:47

Added by:Thanh-Vy Hua
Date:2004-12-24
Time limit:0.180s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Thanh Vy Hua Le, special thanks to my friends in EPS