1474: M的算式

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:122 Solved:40

Description

给出一个算式S,算式中只包含三种运算符:按位取反运算~、按位与运算&、按位或运算|。其中优先级为:~ 大于 & 大于 |。

已知表达式一定合法,且不会出现连续取反的情况,现在M想问你,给定算式的结果是多少。


保证算式一定合法,且没有多余字符,算式的长度<=3*10^5

Input

第一行输入一个数T,表示共有T组数据。
接下来T行每行一个字符串S,表示这个算式。

Output

输出包含T行。
第i行输出表示第i个算式的结果。

Sample Input Copy

2
1|2&3
~1&~3|2

Sample Output Copy

3
6

HINT

特别的是,算式中出现的数值,是恰由3位二进制机器码表示的非负整数,例如数值2对应的机器码为010、数值5对应的机器码为101。