#216176. [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 (), which is the number of test cases.

Each of the next lines describes test cases, consisting of four triangles each, one triangle per line. Each triangle consists of three integers , and (). 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 , and , then the input would be . The integers will not necessarily be perfect squares. It is guaranteed that the given triples each represent a triangle of positive area.

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

样例输入 1

3
1 1 2
2 1 1
2 1 1
1 2 1
1 1 1
1 1 1
1 1 1
1 1 1
5 125 130
125 20 145
45 130 145
145 145 80

样例输出 1

1
0
1