Watson gives a circle and a triangle in a 2-dimensional plane to Sherlock. Sherlock has to tell if they intersect/touch each other.

The circle is centered at $(x_c,y_c)$ and has radius $\mbox{R}$.

Input Format

The first line contains $\mathbf{T}$, the number of test cases.

Each test case consists of $x_c$, $\boldsymbol{y}_{c}$ and $\mbox{R}$ in one line.

The next three lines each contains $x_i,y_i$ denoting the vertices of the triangle.

Output Format

For each test case, print YES if the triangle touches or intersects the circle; otherwise, print NO.

Constraints

$1\leq T\leq30000$

$1\leq R\leq2000$

$-2000\leq x_c,y_c\leq2000$

$-5000\leq x_i,y_i\leq5000$

Note: There will be no degenerate triangles (i.e. triangles with area 0)

Sample Input

2
0 0 10
10 0
15 0
15 5
0 0 10
0 0
5 0
5 5

Sample Output

YES
NO

Explanation

In the first case, the triangle is touching the circle. In the second case, it neither touches nor intersects the circle.

见题面

见题面