问题描述

求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。

规则说明

• 加、减、乘、除、乘方分别用+，-，*, /, ^表示
• 表达式可以有圆括号()
• 时间限制：1000ms
• 内存限制：65536KB
• 乘方的优先级比乘除都高，结合性是向左结合，如2 ^ 3 ^ 4表示( 2 ^ 3 ) ^ 4 = 4096
• 除法的商向下取整
• 不必考虑除0、溢出情况，每个运算数可由int放下

输入

第一行为测试数据的组数N。 接下来的N行，每行是一个中缀表达式：

• 圆括号、运算符和运算数相互之间都用空格分隔
• 运算数是整数，可正可负（负数的符号和数字之间无空格）
• 指数一定为自然数(0和正整数)
• 中缀表达式的字符串长度不超过600

输出

对每一组测试数据输出一行，为表达式的值

样例输入

2
31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2
2 * 5 + 6 * ( 7 - 8 ) + 6

样例输出

4373
10