问题描述
阅兵式上，国王见到了很多新奇东西，包括一台安卓手机。他很快对手机的图形解锁产生了兴趣。
解锁界面是一个 $3 \times 3$ 的正方形点阵，第一行的三个点标号 $1, 2, 3$，第二行的三个点标号 $4, 5, 6$，第三行的三个点标号 $7, 8, 9$。密码本身是一段序列，表示经过点的先后顺序，但遵循如下规则：
1. 密码至少经过四个点。
2. 不能重复经过同一个点。
3. 路径上的中间点不能跳过，除非已经被经过（$3427$ 是合法的，但 $3724$ 不合法）。
他想设置的密码的长度为正整数 $k(1\le k\le 9)$，密码序列为 $s_1 s_2...s_k(0\le s_i < INT\_MAX)$，他想知道这个密码序列是否合法，这个问题交给了你。
输入描述
第一行一个整数表示测试组数：$T(0 < T\le100000)$ 。
每组数据占一行，每行第一个数 $k$，设置密码的长度；接着 $k$ 个正整数，之间用空格隔开，表示密码序列 $s_1s_2...s_k$。
输出描述
共 $T$ 行。对每组数据，若合法输出 `valid`，否则输出 `invalid`。
输入样例
3
4 1 3 6 2
4 6 2 1 3
4 8 1 6 7
输出样例
invalid
valid
valid
Hint
对于第一组数据，$1$ 到 $3$ 跳过了路径上的点 $2$，所以不合法。
对于第二组数据，$1$ 到 $3$ 时点 $2$ 已经被经过了，所以合法。
对于第三组数据，$8\rightarrow 1 \rightarrow 6 \rightarrow 7$ 路径均没有中间点，所以合法。
