## Data Structure 2

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
```

## Comments