Problem L
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.

Figure 1: A solution to the third test case in the sample input.

Input

The first line of input contains a single integer $t$ ($1 \leq t \leq 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 \leq a,b,c \leq 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

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.

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
0
1