URI Online Judge | 1618

Colision

By Jony Teixeira de Melo, Centro Universitário do Triângulo BR Brazil

Timelimit: 1

You have been tasked to check if the robot invaded a rectangular area formed by four cardinal points (A, B, C and D). Will be informed the four cardinal points of a plan as shown. The area is formed by connecting the four points as follows AB, BC, CD and DA. The X, Y coordinate of the robot will be informed

Input

The input consists of several test cases. The first line is formed by a number N indicating the total number of test cases. The next N lines consist of 10 integers (Ax, Ay, Bx, By, Cx, Cy, Dx, Dy, RX, RY) representing each of the vertices A, B, C and D and the location X, Y robot. Each value is separated by a blank space.

Output

The output should print for each test case, the number 1 if the robot is within the area (considering the edges of the figure as part of the area of the figure) , and print the number 0 otherwise.

Sample Input Sample Output

5

3 6 6 6 6 5 3 5 5 4

1 1 7 1 7 7 1 7 4 2

1 4 7 4 7 6 1 6 5 5

6 2 9 2 9 6 6 6 1 7

4 3 9 3 9 5 4 5 10 7    

0

1

1

0

0