Geometry Problem

Tired of all the geometry problems in programming contests, you decided to leave contests and get into game development. There were more geometry problems waiting for you anyway. You designed a two player 2-D arcade game. The first player throws a triangular metal piece in a chosen direction. The second player then throws another triangular metal piece to hit the first player's piece. You want to know whether the two pieces will collide.

At the instant the second player throws his piece, you store the position and velocity of both pieces and call this time 0. The game does not allow the pieces to already be in collision at time 0. Compute the time at which the two pieces collide.

The first line contains $T$, the number of test cases. Each test case has two lines. The first line describes the first player's piece, and the second line describes the second player's piece. Each description has 8 space separated integers $x_1, y_1, x_2, y_2, x_3, y_3, v_x, v_y$. $(x_i, y_i)$ is the position of the $i$-th vertex of the piece, and $v_x$ and $v_y$ are the x and y components of the piece's velocity.

For each test case, print one line with the earliest time at which the two pieces collide. The answer must have a relative or absolute error of at most $10^{-9}$. If the pieces never collide, print "NO COLLISION" (without quotes).

$1 \le T \le 100$

$-10^7 \le x_1, y_1, x_2, y_2, x_3, y_3, v_x, v_y \le 10^7$