F. 3D Triangles 

The Problem

Given the vertices of two triangles in 3D Coordinates, check whether both of them have any common point. All points on the edges or vertices are considered to be part of the a triangle. Two points are considered to be the same point if their Euclidean distance is less or equal to 0.000001.

The Input

Input starts with an integer t (t<= 100000) denoting the number of test cases to follow. Each test case contains 18 floating point numbers with at most 7 digits after the decimal. They are the vertices of the triangles as (x, y , z). First three triples are for one triangle and rest of them are for the other one. None of the triangles will be invalid.

The Output

For each input value, output 1 on a single line if the triangles share a common point. Otherwise, output 0.

Sample Input

2
0.366955 0.566515 0.398724
0.573168 0.175512 0.873745
0.705588 0.374035 0.072390
0.292306 0.515061 0.371929
0.623737 0.169012 0.514115
0.839076 0.717612 0.255867
0.039521 0.379528 0.617084
0.759484 0.836268 0.097446
0.594165 0.484085 0.191534
0.283731 0.896054 0.182867
0.443800 0.472579 0.899808
0.473342 0.573901 0.769219

Sample Output

1
0

Problem setter: Josh Bao
Alternative Solution: Mike Liu