Valid Parentheses Checker

This problem requires you to determine whether a given string of parentheses is valid. A string containing only characters '(', ')', '[', ']', '{', '}' is considered valid if:

• Every opening bracket has a corresponding closing bracket of the same type.
• Opening brackets appear in the correct order so that they are properly nested.

Formally, a parentheses string s is valid if it satisfies the following condition in LaTeX:

$$\text{For every prefix } s[1\ldots k], \text{ the number of opening brackets is at least as many as the number of closing brackets of each type.} $$

Your task is to implement a solution that reads multiple test cases from standard input and outputs the validation result for each test case on a new line.

inputFormat

The first line of input contains an integer T indicating the number of test cases.

Each of the next T lines contains a string consisting solely of the characters '(', ')', '[', ']', '{', '}'.

Input is read from stdin.

outputFormat

For each test case, print "Valid" if the input string is valid, otherwise print "Invalid". Each result should be output on a separate line to stdout.

## sample

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

Valid
Valid
Invalid

</p>