Problem Description

In a military parade, the King sees lots of new things, including an Andriod Phone. He becomes interested in the pattern lock screen.

The pattern interface is a $3 \times 3$ square lattice, the three points in the first line are labeled as $1, 2, 3$, the three points in the second line are labeled as $4, 5, 6$, and the three points in the last line are labeled as $7, 8, 9$。The password itself is a sequence, representing the points in chronological sequence, but you should follow the following rules:

- The password contains at least four points.


- Once a point has been passed through. It can't be passed through again.

- The middle point on the path can't be skipped, unless it has been passed through($3427$ is valid, but $3724$ is invalid).

His password has a length for a positive integer $k (1\le k\le 9)$, the password sequence is $s_1,s_2...s_k(0\le s_{i} < INT\_MAX)$ , he wants to know whether the password is valid. Then the King throws the problem to you.

Input

The first line contains a number&nbsp;$T(0 < T \le 100000)$, the number of the testcases.

For each test case, there are only one line. the first first number&nbsp;$k$，represent the length of the password, then $k$ numbers, separated by a space, representing the password sequence $s_1,s_2...s_k$.

Output

Output exactly $T$ lines. For each test case, print `valid` if the password is valid, otherwise print `invalid`

3
4 1 3 6 2
4 6 2 1 3
4 8 1 6 7

invalid
valid
valid

hint:
For test case #1：The path $1\rightarrow 3$ skipped the middle point $2$, so it's invalid.

For test case #2：The path $1\rightarrow 3$ doesn't skipped the middle point $2$, because the point 2 has been through, so it's valid.

For test case #2：The path $8\rightarrow 1 \rightarrow 6 \rightarrow 7$ doesn't have any the middle point $2$, so it's valid.