Square

Interview

Time limit1sMemory limit512 MB

Summary

Given four points per test case, decide whether they can form the vertices of a square using pairwise distance checks.

Level: Medium4 of 10
Topics: Geometry, Math, Brute force
Solved: No attempts yet

Problem

You are given the coordinates of four distinct points. Determine whether all four points can be used as the vertices of a square.

Input

The first line contains the number of test cases, T. Each test case consists of four lines. Each of those lines contains the coordinates x y of one point. Every coordinate is an integer between -100000 and 100000, inclusive, and no point appears more than once in the same test case.

Output

For each test case, print 1 on its own line if the four given points can form a square. Otherwise, print 0.

Examples1

Example 1
Input
```
2
1 1
1 2
2 1
2 2
2 2
3 3
4 4
5 5
```
Expected output
```
1
0
```