Description

输入一串括号表达式，计算括号是否匹配。
括号包含(,),[,],{,}。

Input

输入的第一行是一个int型整数T，表示一个有T组数据。
接下来T行，每行一个一个表达式。

Output

输出T行，每行一个整数，匹配输出1，不匹配输出0。

Sample Input

2
(())[]{}
(())[{]}

Sample Output

1
0