Competitions

# Stack Data Structure

# Parentheses Balance

You are given a string consisting of parentheses **( )** and **[ ]**. A string of this type is said to be correct:

- if it is the empty string
- if
**A**and**B**are correct,**AB**is correct, - if
**A**is correct, (**A**) and [**A**] is correct.

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is **128**.

#### Input

The first line contains the number of test cases **n**. Each of the next **n** lines contains the string of parentheses **( )** and **[ ]**.

#### Output

For each test case print in a separate line "**Yes**" if the expression is correct or "**No**" otherwise.

Input example #1

3 ([]) (([()]))) ([()[]()])()

Output example #1

Yes No Yes