Template Tag Audit

Problem

A page template engine fails the whole render when one section tag is left open or closed in the wrong place. Tags come in three kinds. Each opening tag is a single character, and so is its closing tag: ( closes with ), [ closes with ], and { closes with }.

A line is well formed when every tag that opens is closed by its own kind, and tags close in the reverse of the order they were opened. Lines are never empty. For each line, decide whether it is well formed.

Input

The first line has an integer t, the number of lines to check. Each of the next t lines holds one non-empty string made only of the six characters ( ) [ ] { }.

Output

Print t lines. For each string print YES if it is well formed, otherwise NO.

Constraints

• 1 ≤ t ≤ 100000
• Each string has length at least 1.
• The total length of all strings is at most 200000.

Notes

In the first line ([]{}), the [ closes with ] and the { closes with } before the outer ( closes with ). Every tag is closed by its own kind, in the reverse order of opening, so the answer is YES.