1 s   128 MB

Description

Your job is to write a program of solving a simple geometry problem for finding the number of intersection points of the boundary of a rectangle and a line segment. Each edge of a given rectangle is parallel to x-axis or y-axis. (You are very lucky!) The number of intersections between them is zero, one, two, or infinity. A case of ‘infinity’ occurs in a situation in which an edge of the rectangle and the segment are overlapped partially or wholly. See the figure below which shows examples of several situations between a rectangle and a segment.

(a) Some examples of zero intersection between R and l.

(b) Some examples of one intersection between R and l.

(c) Some examples of two intersections between R and l.

(d) Some examples of infinite intersections between R and l.

Figure 1. Examples of several situations between a rectangle R(blue) and a line segment l(red).

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with four integers xmin, ymin, xmax, and ymax representing a recrangle R, where (xmin, ymin) and (xmax, ymax) represent the coordinates of the lower left corner and upper right corner of R, respectively, -10,000 ≤ xmin < xmax ≤ 10,000 and -10,000 ≤ ymin < ymax ≤ 10,000. The next line contains four integers x1, y1, x2, and y2 representing a line segment l, where (x1, y1) and (x2, y2) represent the coordinates of two end poiunts of l, respectinely, -10,000 ≤ x1, y1, x2, y2 ≤ 10,000, and the length of l is greater than zero.

Output

Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer representing the number of the intersections of the boundary of a rectangle and a line segment given by input. If the number of the intersections is infinity, then your program should output "4" instead.

Sample Output

16
0 0 8 4
2 6 -2 3
0 0 8 4
0 4 9 4
0 0 8 4
3 5 6 6
0 0 8 4
-2 5 10 -1
0 0 8 4
0 5 8 5
0 0 8 4
4 3 4 1
0 0 8 4
-2 3 2 5
0 0 8 4
2 4 6 4
0 0 8 4
0 4 4 7
0 0 8 4
4 2 4 4
0 0 8 4
4 2 8 4
0 0 8 4
0 2 3 4
0 0 8 4
-4 0 12 4
0 0 8 4
4 8 4 -1
0 0 8 4
0 -2 0 6
0 0 8 4
3 4 10 4
0
4
0
2
0
0
1
4
1
1
1
2
2
2
4
4

Source

2014 ACM-ICPC Asia Korea Internet Competition F