A string of parentheses is said to be valid if it satisfies one of the following rules:
(1) The string is an empty string.
(2) If strings S and T are both valid, then ST is valid.
(3) If a string S is valid, then {S}, [S], (S) and <S> are valid as long as S does not contain any parentheses with higher precedence than its enclosing parentheses. The precedence order of parentheses from high to low is { }, [ ], ( ), < >. Therefore, a string of {[]()} is valid, but a string of {([])} is not.
Given a string consisting of parentheses, determine if it is a valid string.
The first line of the input contains an integer N (N ≤ 10000) denoting the number of test cases. Each of the next N lines corresponds to a test case, which contains a string of parentheses, and the maximum string length is no more than 1000 characters. Note that an empty string (a line which contains the newline character only) may be present in the input and it should be considered as a valid string according to rule (1).
Difficulty level 1: N <= 10
Difficulty level 2: N <= 50
Difficulty level 3: N <= 100
Difficulty level 4: N <= 1000
Difficulty level 5: N <= 10000
For each test case, print in each line a "Yes" or a "No" to indicate that the string is valid or not.