Description

一个括号字符串，其中仅包含三种括号(),[],{},括号可以嵌套使用，给定T组括号字符串，请判断每组字符串中的括号是否都正确匹配。正确匹配的规则如下： 1、每一对括号必须先左后右、成对出现； 2、每一对括号内的括号也要满足规则1。

例如：括号字符串[{()}[()]]是正确匹配，而{}是错误匹配，因为"{[}"中“["不成对。

Format

Input

第一行包含一个整数T； 接下来T行，每行一个字符串，表示要判断的括号字符串。

数据范围： 测试点1~10:1<=T<=20,1<=括号字符串长度<=255。

Output

共T行，每行一个字符串，表示判断结果，如果对应行的字符串正确匹配，则输出“YES”，否则输出“NO”。

Samples

3
[]{()}
[{}(]){}
(()[]

YES
NO
NO

Limitation

1s, 1024KiB for each test case.