Problem Description

You are given the squares of the side lengths of four triangles.

Determine whether the four triangles can be arranged into a square using translation, rotation, and reflection.

Requirements:

• triangles may not overlap,
• there may be no gaps or holes.

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases.

Each test case consists of four lines, one for each triangle.

Each triangle is given by three integers a, b, c:

• 1 <= a, b, c <= 10^7

Each number is the square of a side length of the triangle.
For example, if a triangle has side lengths 3, 4, and 5, then its input would be:

9 16 25

The values a, b, and c themselves do not need to be perfect squares.

It is guaranteed that every triple describes a triangle with positive area.

Output

For each test case, output one line containing:

• 1 if the four triangles can be arranged into a square,
• 0 otherwise.

Sample Input 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

Sample Output 1

1
0
1