Arithmetic Expression Validation

You are given a set of arithmetic expressions. Each expression is a string consisting of digits (0–9) and the operators '+' and '*'. An expression is considered valid if it meets all of the following conditions:

• The expression is non-empty.
• The first and the last character of the expression are digits (i.e. they are not '+' or '*').
• The expression contains only digits and the operators '+' and '*'.
• No two operators appear consecutively.
• The total count of the '+' operator does not exceed 2.
• The total count of the '*' operator does not exceed 3.

In mathematical terms, if we denote by \(E\) the expression, and let \(n_{+}\) and \(n_{*}\) be the counts of '+' and '*' respectively, then a valid expression satisfies:

[ E \neq ""; \quad E[0] \notin {+, *}; \quad E[|E|-1] \notin {+, *}; ] [ \text{For all adjacent symbols } c_i \text{ and } c_{i+1},; {c_i, c_{i+1}} \not\subset {+, }; ] [ n_{+} \le 2, \quad n_{} \le 3. ]

Your task is to write a program that reads a list of expressions and determines for each whether it is Valid or Invalid according to the rules above.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer T representing the number of expressions.
2. Each of the next T lines contains a single arithmetic expression (a string).

outputFormat

For each expression, output a line containing either Valid if the expression meets all the validity criteria, or Invalid otherwise. The output should be written to standard output (stdout).

## sample

5
12+7*3
15+35+21
3*5*7*
123*456+789
1000+200*5

Valid
Valid
Invalid
Valid
Valid

</p>