题目描述

众所周知，米池是一个很坑的池子，他要九十抽才保底，保底还会歪！！！！小安是个非酋，一直妄想自己能当个欧皇，每次结果都不尽人意，这导致他很抓狂，于是他想试试你们的实力，看你们会不会抓狂。 已知米池抽卡中，可能抽到的有三星武器，四星角色或武器，五星常驻角色或武器，五星限定角色或武器，下面分别用 $3$，$4$，$5$，$u$ 来表示这四种，已知米池抽卡有如下三种原则: 1.十次抽卡内不会只有三星 $2.90$ 次抽卡内必出五星，可能是限定可能是常驻。 3.两次相邻的五星必定有一个限定。相邻不是挨着出，而是抽出的两个五星，即中间可能会有一些三星或四星。 现在小安给出你一些抽卡记录，请你判断该记录是否是合法的抽卡。

输入格式

第一行一个整数 $t$，表示测试用例数。($1<=t<=10$^$3$^) 随后 $t$ 行，每行一个字符串，只包含 $3$，$4$，$5$，$U$，表示一个抽卡记录。字符串长度不超过 $10^4$^

输出格式

输出 $t$ 行，每行一个字符串，对于每一个测试用例，如果合法就输出"valid"，不合法则输出”invalid”。

样例

样例输入 1

5
433333333334
34343453434
333335333335
UUUUUUUUUU
5U5U5U5U5U4

样例输出 1

invalid
valid
invalid
valid
valid