## Description:

There are six kinds of brackets: ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{’, ‘}’. dccmx’s girl friend is now learning java programming language, and got mad with brackets! Now give you a string of brackets. Is it valid? For example: “(([{}]))” is valid, but “([)]” is not.

## Input:

First line contains an integer T (T<=10): the number of test case.

Next T lines, each contains a string: the input expression consists of brackets.

The length of a string is between 1 and 100.

## Output:

For each test case, output “Valid” in one line if the expression is valid, or “Invalid” if not.

## Sample Input:

2

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

({[}])

## Sample Output:

Valid

Invalid

## Note:

本题由旧版NOJ导入，来源：NUPT ACM 2010 Personal Ranking Contest