Coco 的巧克力店里卖的巧克力因甜美而闻名。因此，Coco 打算在店门前贴上如下的警告标语。

仔细看着这个标语的 Coco 意识到，如果删掉感叹号之间的文字，并在该位置放入一个数字，就会变成一种数学表达式。让我们来计算这个表达式。

在本题中，需要计算的表达式由一个整数和 $0$ 个或多个感叹号组成。整数为 $0$ 或 $1$，感叹号可以出现在整数的前面或后面。计算该表达式的规则如下：

• $n!$ 表示 $n$ 的阶乘。定义为 $0! = 1$，$1! = 1$。
• $!n$ 表示 $n$ 的逻辑非（logical not）。定义为 $!0 = 1$，$!1 = 0$。
• 如果阶乘或逻辑非有多层嵌套，则计算相应嵌套次数。如果两者同时使用（例如 $!n!$），则优先计算阶乘。例如，$!!n!! = !(!((n!)!))$。

输入格式

第一行给出表达式的数量 $T$。$(1 \le T \le 1\,000)$

从第二行开始，给出 $T$ 个表达式，每行一个。每个表达式由 $a$ 个感叹号、整数 $n$、以及 $b$ 个感叹号无空格地按顺序拼接而成。$(0 \le a, b \le 30;$ $0 \le n \le 1)$

输出格式

对每个表达式，在一行中输出其计算结果。

样例

输入样例 1

6
0!
1!
!0
!1
!!0!!
!!1!!

输出样例 1

1
1
1
0
1
1