逻辑表达式

时间限制：$1000ms$

空间限制：$256MB$

题目描述

这个学期$lhy$正在学习数字逻辑电路，逻辑代数是一个重点。$lhy$作为一名计电院的学生，十分喜欢使用计算器，但是很可惜，一般的计算器都不支持逻辑运算。于是$lhy$找到了你，想和你合作写一个可以实现逻辑运算的计算器，减少学习的痛苦。$lhy$已经完成了大部分工作，现在还缺少一个计算逻辑表达式的算法，你将这部分完成就可以了。

按照$lhy$的接口设计，算法的输入包含一个逻辑表达式和一组赋值，算法的输出是一个确定的逻辑常量。

逻辑常量，只有$0$和$1$两种，表示对立的状态。

逻辑变量，一些由字母表示的量，类似于代数中的变量$x,y,z$等，但是这里的逻辑变量只能取$0$和$1$两种。 赋值，给逻辑变量取定一个值称为赋值，比如下表(逻辑运算符中)就是$4$组不同的赋值。

逻辑运算符，只需要包含如下三种即可：与(&),或(|),非(!)，优先级为非最高，与或同级。

逻辑表达式，包含逻辑常量，逻辑变量，逻辑运算符以及括号。与一般的代数式相同，括号可以改变式子的运算顺序。

注意，$lhy$会保证输入的逻辑表达式一定是合法的，所有的赋值是唯一的，不会出现没有赋值的逻辑变量。

此外，由于在python中，and的优先级是在or之上的，而本题要求二者同级，所以你并不能直接使用内置的$eval$函数。

数据格式

输入

第一行，一个正整数$T$，表示测试用例的数量。

每个测试用例的输入如下：

第一行，一个合法的逻辑表达式$expression$。

第二行，一个非负整数$n$，表示逻辑表达式含有的逻辑变量个数。

接下来$n$行，每行一个字符$key$和一个逻辑常量$value$，表示名为$key$的逻辑变量取值为$value$.

输出

一个逻辑常量。

样例1

输入

4
1|0&0
2
a 1
B 0
!(t|r|a|t|S)&!(t|c|a|p|m|I|n|i|h|s|n|e|G)
14
G 0
e 0
s 0
h 0
i 0
n 0
I 0
m 0
p 0
c 0
S 0
a 0
r 0
t 0
(H&o|n|k&|a&!i|S|!t|a|r&R&a&i|l)
11 
H 0
o 1
n 0
k 0
S 0
t 0
r 0
R 1
a 1
i 1
l 0
n&n&u
52
a 1
b 0
c 0
d 0
e 1
f 1
g 0
h 1
i 0
j 1
k 1
l 1
m 0
n 0
o 1
p 1
q 0
r 0
s 1
t 1
u 1
v 1
w 1
x 0
y 1
z 0
A 1
B 1
C 1
D 1
E 1
F 0
G 1
H 1
I 0
J 0
K 1
L 0
M 0
N 1
O 0
P 1
Q 1
R 1
S 1
T 0
U 0
V 0
W 0
X 0
Y 0
Z 1

输出

0
1
1
0

数据范围及约定

数据保证$key$的命名只取小写字母$a$~$z$以及大写字母$A$~$Z$，共计$52$种.

数据保证表达式的长度之和$\sum|expression|$不超过$10^6$.

数据中的逻辑变量不一定按照出现的顺序赋值，也可能会有冗余的赋值。