输入格式

第一行，一个整数 $T$ ，表示案例的个数。

接下来的 $T$ 行，每行一个字符串（长度小于等于 $100$ ），字符串仅由 $0-9,+,-,*,/,$ ^ $,!$ 字符组成，数字表示一个数值，范围为 $[0,9]$ ，且数字不存在前导零，其他符号表示一种运算规则，规则的描述如下：

$+$ ：数字 $1 +$ 数字 $2 =$ 两个数字之和， $+$ 号的优先级为 $1$ ;

$-$ ：数字 $1 -$ 数字 $2 =$ 两个数字之差， $-$ 号的优先级为 $1$ ;

$*$ ：数字 $1 * $ 数字 $2 = $ 两个数字之积， $ * $ 号的优先级为 $2$ ;

$/$ ：数字 $1 /$ 数字 $2 =$ 两个数字之商（舍去小数）， $/$ 号的优先级为 $2$ ;

^：数字 $ 1 $ ^数字 $2 =$ 数字 $1$ 的数字 $ 2$ 次方， ^ 号的优先级为 $3$ ;

$!$ ：数字 $1 ! =$ 数字 $1$ 的阶乘， $!$ 号的优先级为 $4$ 。

按照优先级从高到低的顺序依次计算，同级运算时，从左到右依次计算。

输入保证对于每个字符串，满足上述条件，一行输入，以换行符结束。保证式子的表达式语义正确。

特别的，一切数值计算均受限于模 $65536$ 的数域，即每一步运算都要对 $65536$ 取模，取模的规则同C语言规范。

同时，任意数的 $0$ 次方等于 $1$ 。

输出格式

$T$ 行， $T$ 个整数。

每行输出对应案例表达式运算的结果，如遇到除以 $0$ 的算数错误，请输出ArithmeticException。

1
4*3/2^0+9

2
2!!
3/2^4^4

2
ArithmeticException

对于 $100%$ 的数据，保证 $1 \le T \le 10^5$ 。

来源/分类

分治字符串