#1293 Aircraft

23  2 s   128 MB  

Description

In aviation, a "near miss" occurs if the distance between two aircraft at some point in time is less than or equal to some threshold distance R. At a moment in time, the positions and velocities of two aircraft are known exactly. Assuming that each aircraft continues to fly with constant speed and direction, you need to work out if the aircraft will undergo a near miss now or at some point in the future. 

You will be given the threshold distance R and the positions and velocities of the aircraft in four arrays of integers: p1, v1, p2 and v2. The position of the first aircraft in 3-D cartesian space is given by (p1[0] , p1[1] , p1[2]) and its velocity vector by (v1[0] , v1[1] , v1[2]) and similarly the second aircraft's position and velocity are given by (p2[0] , p2[1] , p2[2]) and (v2[0] , v2[1] , v2[2]). So, if an aircraft's initial position is the vector p and its velocity vector is v, the position of this aircraft at some future time t will be p + v * t. You should print "YES" if the aircraft will undergo a near miss now or in the future or "NO" if they won't (quotes for clarity).

Input

The first line contains the number of test cases T (T ≤ 250).

For each test case, R (0 <= R <= 10000) will be given on the first line.

On the next line, 12 integers will be given: p1[0], p1[1], p1[2], v1[0], v1[1], v1[2], p2[0], p2[1], p2[2], v2[0], v2[1], v2[2]. Each value will be between -10000 and 10000, inclusive.

Output

Output the answer of each test case on a separate line.

Sample Input

Sample Output

2
5
0 0 0 2 2 0 9 0 5 -2 2 0
5
0 0 0 -2 2 0 9 0 5 2 2 0
YES
NO