Problem Description

Given four three-dimensional vectors $A_1, A_2, A_3, A_4$, determine whether there exist non-negative real numbers $x_1, x_2, x_3$ that satisfy the following equation:

$$x_1A_1 + x_2A_2 + x_3A_3 = A_4$$

Here, $A_i = (a_{i1}, a_{i2}, a_{i3})$ represents the components of the three-dimensional vector $A_i$.

For example, $A_1=(3,4,4)$, $A_2=(4,3,0)$, $A_3=(2,3,2)$, $A_4=(9,10,6)$ has a non-negative solution because $A_1+A_2+A_3 = A_4$.

Input

The first line contains an integer $T$ $（1 \leq T \leq 1000）$, representing the number of test cases.

Each test case consists of a single line containing $12$ integers in $a_{11}, a_{12}, a_{13}, a_{21}, a_{22}, a_{23}, a_{31}, a_{32}, a_{33}, a_{41}, a_{42}, a_{43}（0 \leq a_{ij} \leq 10^4,1\leq i \leq 4,1\leq j \leq 3）$, representing the components of the four three-dimensional vectors $A_1, A_2, A_3, A_4$.

Output

For each test case, output a single line containing either "YES" or "NO", indicating whether a non-negative solution exists.

If a non-negative solution exists, output "YES"; otherwise, output "NO".

2
3 4 4 4 3 0 2 3 2 9 10 6 
0 3 1 0 1 3 4 0 4 4 1 10 

YES
NO