题目描述

为了让幻想乡的妖怪们更富有智慧，贤者八云紫决定在幻想乡开设计算机基础、C语言程序设计、数据结构等课程。琪露诺听说课上可以玩电脑，于是兴冲冲地把大妖精拉上，报名参加了C语言基础课程。
琪露诺当然什么都听不懂（毕竟她的智商只有⑨），所以每次上课她都全程跟大妖精玩昆特牌，下课后请其他妖怪帮她写作业。⑨个月后她把雾之湖所有的妖怪和妖精都委托了一遍，现在她找不到别人，只能再次找你了。
这次的作业是这样的：给你一个括号序列，其中有圆括号()、方括号[]、花括号{}和尖括号<>，请问该序列是否合法。
合法的括号序列可以按如下方式递归定义：
（1）空序列是合法的；
（2）若A和B是合法的括号序列，则AB（将B连接到A的后方）也是合法的括号序列；
（3）若A是合法的括号序列，则在两端添加一对括号，(A)、[A]、{A}、<A>都是合法的括号序列。

输入格式

第一行是一个正整数\(T\)，表示数据组数；
之后\(T\)行，每行包含一个字符串，表示待判断的括号序列。保证字符串非空且只会包含()[]{}<>这8种字符。

输出格式

对于每组数据，若该序列是合法的则输出Yes，否则输出No。

样例

输入

3
(([]))
([(]))
{<><>}<{{(}}>)

输出

Yes
No
No

数据规模及约定

\(T \le 10^5\)，所有测试数据的序列长度之和\(\le 10^6\)。
本题共10组测试文件，部分满足如下的附加限制条件：
测试点#1~3：序列中只包含圆括号
测试点#1~6：\(T \le 30\)
测试点#4：每个序列长度\(\le 100\)
测试点#1,5,6：每个序列长度\(\le 1000\)
时间限制1s，空间限制64MB。