Problem Description

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. :::

Input Format

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 Format

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