The Date Format Police

Ferrers Insurance refuses any policy record whose start date is not written the way its warehouse expects, and that check runs before anything tries to interpret the date as a real day. A value passes only if every one of these holds: it is exactly ten characters long, its fifth and eighth characters are dashes, every other character is a digit, its two month characters read from 01 to 12, and its two day characters read from 01 to 31. The check knows about shape and ranges only — it owns no calendar, so 2023-02-31 passes it.

Task: Print whether each value passes the check.

Input

The first line holds one integer n, how many values follow. Each of the next n lines holds one value exactly as it appeared in the file. A value can be any text at all, including text shorter or longer than a date.

Output

n lines in the same order, each holding the lowercase word valid or invalid.

Example:

Input:
4
2023-05-14
2023/05/14
2023-13-01
23-05-14

Output:
valid
invalid
invalid
invalid