Valid Parentheses

1000ms    65536K
22    1
Beginner

Description

Given a string containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Input

There are multiple test cases.

The first line contain a positive integer N. means there are N test cases.

Following N lines, for each line there a string which you need to determine if it's a valid parentheses.

Output

For each line output Valid or Invalid.

Sample Input

3
()
[]
([)]

Sample Output

Valid
Valid
Invalid

Source

Editor

keefo on 2015-01-23 04:33:59


North University of China

OnlineJudge

NUC

NOJ

OJ

ACM/ICPC