Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 22344. Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 774410 we shall call a positive integer that is neither increasing nor decreasing a Invalid number; for example, 155349.WAP to check whether a number is valid or not.

Input
The number of test cases have to be specified in the first input(between 1 to 1000).The input consists of one number given as input at a time,the program checks if the number is vaild or not.

Output
The output displays whether the number is vaild or not,i.e it displays valid when the number is Valid and invalid when its not.

Example

Input:
7
1
2
3
4
5
6
150

Output:
valid
valid
valid
valid
valid
valid
invalid

见题面

见题面