有道难题：另类异或

描述：

对于普通的异或，其实是二进制的无进位的加法。



这里我们定义一种另类的异或A op B, op是一个仅由^组成的字符串，如果op中包含n个^，那么A op B表示A和B之间进行n+1进制的无进位的加法。

下图展示了3 ^ 5 和 4 ^^ 5的计算过程：

0 1 1 (3)

^ 1 0 1 (5)

---------

1 1 0 (6)

0 1 1 (4)

^^ 0 1 2 (5)

---------

0 2 0 (6)

输入：

第一行有一个正整数T, 表示下面共有T组测试数据。

接下来T行，每行有一组测试数据，是由空格隔开的三个部分组成：

A B C

A和C是两个十进制整数，B是一个字符串，由n个^组成

1 <= T <= 100, 0<=A,B<2^30, 1<=n<=1000

输出：

每个测试数据输出一行，包含一个数字，即该数据的结果，用十进制表示。

样例输入：

2

3 ^ 5

4 ^^ 5

样例输出：

6

6

-you dao nan ti