题目描述

给出一个含布尔变量的布尔表达式，请计算其真值表

布尔表达式由布尔变量、小括号与运算符组成。具体来说，表达式的结构定义如下：

• 一个小写英文字符 a ~ z 是一个可以取 0 或 1 的布尔变量，是一个表达式
• 如果 A 是一个表达式，则 (A) 也是表达式
• 如果 A 是一个表达式，则 !A 也是表达式
• 如果 A、B 是表达式，则 A|B、A&B、A^B、A=B 也是表达式

运算符 !、|、&、^、= 的真值表如下：

运算符的优先级从高到低为 !、&、|、^、=。例如：对于表达式 a&!b|c，计算顺序为 (a&(!b))|c。多个相同运算符则从左往右依次计算

现要求枚举表达式中出现过的每个变量的取值并计算表达式，由此得到真值表

输入格式

输入共 $T+1$ 行

第一行一个整数 $T$，表示测试数据的组数

接下来 $T$ 行，每行一个字符串，表示该组数据提供的表达式

输出格式

输出共 $T$ 行

每行为一个长度为 $2^k$，仅由字符 0 和 1 组成的字符串。其中 $k$ 为该组数据所给表达式中不同的布尔变量数量。要求将变量按字典序从小到大排序后依次枚举取值为 0 或 1。可参考样例解释理解

样例数据

样例一

input

1
(p&q)|((q&p)=(q=!p))

output

1001

解释

• $p=0, q=0$ 时表达式值为 $1$
• $p=0, q=1$ 时表达式值为 $0$
• $p=1, q=0$ 时表达式值为 $0$
• $p=1, q=1$ 时表达式值为 $1$

依次输出得到字符串 1001

样例二

input

1
!(!!(!!a|b&c))

output

11100000

样例三

input

1
!(!!(!a|b&c))&(!(((b^c=d=e))))|(a=b)

output

11111111000000001001011011111111

样例四

input

3
(!!!!!!m^!y=!!y^r&m&r=e^!v|!(y)&(y))
!(!!!!(!((!t|!y^(y)&t&t&(y|(!w))))))
(!(!(z|r))=!r|!z)=k|k&(z)&!!r=!!!k|z

output

00110011110000111100110000111100
11111111
10011100

数据范围与约定

子任务编号	分值	特殊性质
$1$	$20$	表达式中不含括号和 ! 运算符
$2$		每个表达式中只有一个变量，且只出现一次
$3$		表达式中不含 ! 运算符
$4$	$40$	无

对于所有数据，有 $1\le T\leq 5$，$1\le$ 表达式长度 $\le 1000$，$1\le$ 每个表达式内本质不同的变量数量 $\le 5$

本题子任务一不进行捆绑测试