Interior Lattice Points

Time limit1sMemory limit128 MB

Summary

Count the lattice points strictly inside each triangle given by three integer vertices, printing zero for collinear points.

Level: Medium4 of 10
Topics: Geometry, Number theory
Solved: No attempts yet

Problem

A lattice point is a point whose coordinates on a rectangular coordinate system are both integers. An interior lattice point of a polygon is a lattice point that lies inside the polygon and not on its boundary. The triangle in the drawing below has six interior lattice points.

Write a program that reads three pairs of coordinates $(x_A, y_A)$ , $(x_B, y_B)$ , $(x_C, y_C)$ , where every coordinate is a non-negative integer no greater than 100. The numbers in a line are separated by exactly one space and come in the order $x_A\ y_A\ x_B\ y_B\ x_C\ y_C$ . The three points are distinct lattice points, but they may be collinear. If the three points form a triangle with non-zero area, print the number of interior lattice points of that triangle. Otherwise print zero. Three collinear points have no interior lattice points.

Input

The first line contains an integer $N$ ( $0 \le N \le 255$ ). $N$ input cases follow. Each input case is a list of six non-negative integers no greater than 100. The six integers $x_A\ y_A\ x_B\ y_B\ x_C\ y_C$ correspond to the coordinates $(x_A, y_A)$ , $(x_B, y_B)$ , $(x_C, y_C)$ .

Output

For every input case, print the number of interior lattice points on one line.

Examples1

Example 1

Input

4
0 0 100 0 100 100
0 0 98 100 100 100
0 0 99 100 100 100
0 0 99 99 100 100

Expected output