P16093 [ICPC 2024 NAC] Square of Triangles

You are given the squares of the lengths of the sides of four triangles. Determine if it is possible to arrange them (via translation, rotation, and reflection) into a square. No triangles may overlap, and there should be no gaps or holes. :::align{center}  Figure L.1: A solution to the third test case in the sample input. :::

The first line of input contains a single integer $ t $ ($ 1 \le t \le 20 $), which is the number of test cases. Each of the next $ 4 \cdot t $ lines describes $ t $ test cases, consisting of four triangles each, one triangle per line. Each triangle consists of three integers $ a $, $ b $ and $ c $ ($ 1 \le a, b, c \le 10^7 $). Each of the integers is equal to the **square** of the length of a side of a triangle. For example, if the three sides of a triangle have lengths $ 3 $, $ 4 $ and $ 5 $, then the input would be $ 9\ 16\ 25 $. The integers will **not** necessarily be perfect squares. It is guaranteed that the given triples each represent a triangle of positive area.

Output $ t $ lines. For each test case in order, output a single line with a single integer, which is $ 1 $ if the four triangles of the test case can be arranged into a square, and $ 0 $ otherwise.