Bracket Validator

Read n strings of brackets. Print VALID or INVALID for each.

Your task

Write a complete program: read the input with input() and print the result with print().

Example

Input

3
()
([)]
{[()]}

Output

VALID
INVALID
VALID