5641：King's Phone

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.

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 exactly $T$ lines. For each test case, print `valid` if the password is valid, otherwise print `invalid`