e-olymp
Competitions

Робота з рядками

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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
([])
(([()])))
([()[]()])()
Output example #1
Yes
No
Yes