U614650 expr

小 D 最近在学习二元逻辑，他想知道如何对一个逻辑表达式求值。 具体而言，逻辑表达式是一个由 `(`、`)`、`!`、`&`、`|`、`^`、`->`、`0`、`1` 组成的字符串。其中 `!`、`&`、`|`、`^` 和 `->` 分别表示非、与、或、异或和蕴含。 或许你并不熟悉这些运算，这里我们给出每种运算的真值表： | `p` | `!p` | | :-: | :--: | | $0$ | $1$ | | $1$ | $0$ | | `p` | `q` | `p&q` | `p\|q` | `p^q` | `p->q` | | :-: | :-: | :---: | :----: | :---: | :----: | | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | | $0$ | $1$ | $0$ | $1$ | $1$ | $1$ | | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | | $1$ | $1$ | $1$ | $1$ | $0$ | $1$ | 小 D 定义“合法的逻辑表达式”为满足如下条件的表达式： 1. `0` 和 `1` 是合法的逻辑表达式，其值为其本身。 1. 若 `A` 和 `B` 分别是两个合法的逻辑表达式，则 `(A&B)`、`(A|B)`、`(A^B)` 和 `(A->B)` 都是合法的逻辑表达式，其值为将 `A` 和 `B` 的值做对应逻辑运算的结果。 1. 若 `A` 是合法的逻辑表达式，则 `(!A)` 是合法的逻辑表达式，其值为 `A` 的值取反后的结果。 现在，小 D 遇到了一个合法的逻辑表达式，但是他不会对这个表达式求值，于是只能求你帮忙。

第一行一个整数 $T$，表示数据的组数。 接下来 $T$ 行，每行给出一个长度为 $n$ 的字符串。

输出 $T$ 行。 每行输出一个字符 `0` 或 `1`，表示该组数据的答案。

#### 数据范围 对于全部测试点：$1\le T\le 10^3$，$1\le n\le 10^6$，保证单个测试点内所有测试用例 $n$ 的总和不超过 $10^6$。 | 测试点编号 | $n$ | 特殊性质 A | 特殊性质 B | | :---------: | :--------: | :--------: | :--------: | | $1\sim 8$ | $\le 10^3$ | 是 | 是 | | $9\sim 12$ | $\le 10^6$ | 是 | 是 | | $13\sim 16$ | $\le 10^6$ | 是 | 否 | | $17\sim 20$ | $\le 10^6$ | 否 | 是 | 特殊性质 A：字符串中不存在 `!`。 特殊性质 B：字符串中不存在 `->`。