You are given the coordinates of the vertices of a square in the 2-d plane. All vertex coordinates will be integers.

Now consider all convex quadrilaterals which also have integer coordinates for their vertices such that the midpoints of their edges are the vertices of the original square. Find the sum of areas of all such quadrilaterals.

Input

The first line of input gives T, the number of test cases (1≤T≤25000). Following this are the descriptions of the individual testcases. Each testcase consists of four lines, each line containing two space separated integers - the x and y coordinates of a distinct vertex of the square. The coordinate limits are -1000000000≤x_i, y_i≤1000000000. It is assured that the four vertices will correspond to a square.

Output

For each testcase output the total area of quadrilaterals with the given property. Since the answer could be very large, give the answer modulo 100000007.

Example

Input:
2
0 0
1 1
1 0
0 1
0 1
1 0
0 -1
-1 0

Output:
0
4