This practice problem will require you to utilise Stack to solve the bracket matching problem.

Brackets are used in many places, and in this task your job is to make sure the three types of brackets are syntactically correct. The rules are very simple, matching pairs of brackets are considered valid.

E.g. the following brackets are valid:

()[{}]
[[]]

The following is invalid:

[]]
({)}

OJ question csci125p020 only asks you to detect validity for a single type of bracket. In this question you will need to do so for all three types using Stack. You will need to implement a stack as you like first, then use it to solve this question.

Input Specification

The first line contain a single number \(N\) (\(N<1000\)), indicating the number of test cases.

Each line will contain a single test case. Each case will contain no more than 200 characters without whitespace.

Output Specification

The output should contain the \(N\) lines, each line either Valid or Invalid, indicating whether the sequence is valid.

Sample Input

5
]([((]((({)]}
[]()(({}[(())])[])
[]}}())][[
{)[(}()){[((]}{
{{[{{}}[]]{[[]]()}}}

Sample Output

Invalid
Valid
Invalid
Invalid
Valid