Description

Input

The first line contains a single integer $c$ ($1 \le c \le 10^4$) — the number of test cases. Then $c$ cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of array $t$.

The second line of each test case contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_1 < t_2 < \dots < t_n \le 10^9$) — the meeting moments in the increasing order.

It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, print VALID if the array $t$ is a valid array, or (in other words) exist such real values $v_A$ and $v_B$ ($v_A, v_B > 0$; $v_A \neq v_B$) that array $t$ contains the first $n$ meeting moments of Alice and Bob in the pool.

Otherwise, print INVALID.

You can output the answer in any case (upper or lower). For example, the strings "vALid", "valid", "Valid", and "VALID" will be recognized as positive responses.

7
1
42
4
3 4 6 8
5
1 2 3 4 5
3
999999998 999999999 1000000000
5
4 6 8 12 16
4
6 11 12 14
2
10 30
 
 
 
 
 
 
 
 

VALID
VALID
VALID
INVALID
VALID
INVALID
INVALID

Note

In the first test case, imagine a situation: $v_A = 1$ and $v_B = \frac{29}{21}$. Then, at moment $42$ Alice and Bob will be at point $42$.

In the second test case, imagine a situation: $v_A = \frac{175}{6}$ and $v_B = \frac{25}{6}$. Then, at moment $3$ Alice and Bob will meet at point $12.5$, at $4$ they'll meet at point $\frac{50}{3}$, at moment $6$ they'll meet at $25$ and at moment $8$ — at point $\frac{100}{3}$. Since it's exactly the first $4$ meeting moments. Array $t$ may be valid.

In the third test case, one of the possible situations is $v_A = 25$ and $v_B = 75$.