Description
经历了种种机关的考验，小可可终于来到了主墓室，他发现主墓室墙上还有个非常复杂的机关，组成墓室墙壁的方砖上，均刻有由古代字符和数字组成的图案，每块方砖上一组。小可可发现这些古代字符恰好有二十六种，可以用小写英文字母(‘a’~‘z’)来代替他们，而数字可以用(‘0’~‘9’)代替。经过细致的研究，小可可惊奇的发现这些图案中有一些居然是压缩过的回文串。所谓回文串，就是从左向右读与从右向左读都一样的字符串，比如”abcba”是回文串，而”abcbb”不是回文串。而压缩过的回文串，就是对串中连续重复出现p次的子串A,即”AA…A”(共p次),可以替换为”(A)p”。比如”aababababababb”可以替换为”a(ab)3(ab)3b”(当然也可替换为”a(ab)6b”),这样的压缩方法可以使用多次，也就是说括号是可以嵌套的，比如”a(ab)3(ab)3b”可以进一步压缩为”a((ab)3)2b”。只要找出哪些方砖上刻的是回文串，并按动这些方砖，那么将会开启存有宝藏的密室。现在请你帮助小可可来完成这个艰巨的任务吧。
Input
第一行只有一个正整数T,表示要判断的字符串的个数.接下来T行，每行一个待判断的用压缩方式表示的字符串，字符串只含有小写英文字母(‘a’~‘z’)与括号(‘(’, ‘)’),数字(‘0’~‘9’),注意解压缩后的原串只含小写英文字母，也就是说括号与数字都是压缩产生的。输入数据保证所有数不超过109.保证输入文件不含多余空格。
Output
共T行，如果输入文件中第i个串是回文串，则输出”Yes”(不含双引号),否则输出”No”(不含双引号).
5
a((ab)5)2b
(abb)5(bba)5
((ab)5(c)5(ba)5(asdodsfklj)0)8
((((a)10)10000)10000000)10000000
((abcd)100000(dcba)99999)1
HINT
样例说明：
第二个串展开后为”abbabbabbabbabbbbabbabbabbabba”是回文串
第三个串要注意”(A)0”这种表示方式也是合法的.
第四个串说明在输入串长度允许的范围内，解压缩后的原串可能会很长.
提示：
对30%的数据，每个输入串解压缩后的长度不超过200000。
对100%的数据，T≤20,每个输入串长度不超过300,所有压缩后紧跟在括号后的数(也即重复次数)不超过109,解压缩后串的长度可能超过长整形(PASCAL中int64,C++中long long)能表示的最大整数.