都柏林城市大学（Dublin City University）希望阻止学生和教职员工使用弱密码。安全部门委托你编写一个程序，用于检查某些密码是否满足密码指南委员会（Password Guidelines Council）定义的所有质量要求。

这些要求如下。如果一个密码具备以下属性，则被认为是足够强度的：

• 至少包含一个小写字母。
• 至少包含一个大写字母。
• 至少包含一个数字。
• 至少包含一个来自集合 +_)(*&^%$#@!./,;{} 中的符号。
• 最小长度为 12。

示例：

• 密码 "Aa1_"（不含引号）满足前 4 个要求，但其长度小于 12。
• 密码 "Aa1234567890_" 完全符合要求。

输入格式

在每个测试用例中，你需要处理一批密码。

第一行包含一个整数 $N$，表示要处理的密码数量。

每个密码将占两行。第一行包含一个整数 $S$，表示密码的长度。第二行包含一个长度为 $S$ 的字符序列，即待检查的密码。

密码仅包含字母 a 到 z（包括大写和小写）、数字 0 到 9 以及以下符号：+_)(*&^%$#@!./,;{}（不含引号）。

密码的最大长度为 30 个字符。每个测试用例最多包含 100 个待处理的密码。

输出格式

对于每个密码，如果该密码满足质量要求，则输出一行单词 valid，否则输出 invalid。

样例

输入样例 1

2
4
Aa1_
13
Aa1234567890_

输出样例 1

invalid
valid

输入样例 2

5
18
UtQ.iNlLgT;{f,.GR!
29
yr)Z,pHQ+No,ZfP_z12D2l1*MSTfk
23
.p7hV/Es^aahW%B.1JJouO;
9
c7V!*$1lW
26
a^pBAAxCohQlBv7qDpVeOB%Min

输出样例 2

invalid
valid
valid
invalid
valid