Valid Curly Braces

You are given a series of test cases. In each test case, you receive a string consisting solely of the characters { and }. Your task is to determine whether the curly braces in the string are balanced and properly nested.

A string of curly braces is considered valid if every opening brace { has a corresponding closing brace } and the pairs are correctly ordered. More formally, a string s is valid if it satisfies the following condition:

$$\text{A string } s \text{ is valid if and only if it can be constructed using the rule}$$

• s = "" is valid.
• If s is valid, then {s} is valid.
• If s and t are valid, then their concatenation st is valid.

For example, the strings "{}" and "{{}}" are valid, while "{{}" or "}{" are not.

inputFormat

The input is given via stdin and consists of multiple lines. The first line contains an integer T representing the number of test cases. This is followed by T lines, each containing a non-empty string composed only of the characters { and }.

Example:

3
{}
{{}}
{{}{}

outputFormat

For each test case, output a single line containing either YES if the input string's curly braces are valid, or NO if they are not. The output should be printed to stdout.

Example:

YES
YES
NO

## sample

1
{}

YES

</p>