In Genshin Impact, making wishes is an action trying to obtain some specific character.

In this problem, there are four possible results for making wishes: -star weapon, -star weapon/character, -star non-promotional weapon/character, -star promotional weapon/character. Here, we do not distinguish between weapon and character, and we use , , , and to represent each result, respectively.

There are some rules for making wishes.

•  For every consecutive wishes, it will not only contain -star weapons.

•  For every consecutive wishes, it must contain at least one -star weapon/character, no matter whether it is promotional.

•  For every two neighboring -star weapons/characters, there must be at least one which is promotional. Here, two -star weapons/characters are called neighboring if and only if all wishes between them are not -star weapons/characters.

Now you're given a list of wishes. Determine if it fits in the above rules.

The first line contains one integer  (), representing the number of test cases.

For each test case, one single line contains a string  (), which only contains , , , and .

It is guaranteed that .

For each test case, if it fits in the above rules, output "", otherwise output "".

5
433333333334
34343453434
333335333335
UUUUUUUUUU
5U5U5U5U5U4

invalid
valid
invalid
valid
valid