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 $T(0 < T \le 100000)$, the number of the testcases.
For each test case, there are only one line. the first first number $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`
Sample Input
3
4 1 3 6 2
4 6 2 1 3
4 8 1 6 7
Sample Output
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.
