IOPC1202 - Quadrilaterals

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 ≤ xi, yi ≤ 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

Added by:Raziman T V
Date:2012-01-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://www.codechef.com/IOPC2012/

hide comments
2012-08-20 09:14:12 Neptic
co-ordinates will be in regular order or not? in first test case it is not. plz tell me.
2012-05-09 13:26:04 Ajey Golsangi
Can anyone explain how to find the number of interior grid points of a square ?
2012-03-13 17:41:39 Gaurav Kumar Verma
mine took 3.7sec and AC :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.