TRANSP - Transposing is Fun

## 问题描述 给你一个 $2^a \times 2^b$ 的矩阵，在内存中的存放方式是先存第一行，再存第二行。现在想求他的转置矩阵（也是一样的存储方式），但是只能用交换操作，问需要交换多少步。 ## 输入格式 第一行 $1$ 个整数，表示测试数据的组数。 接下来每行 $2$ 个整数，表示 $a$ 和 $b$。 ## 输出格式 对于每组测试数据，输出一行一个数，表示最少的交换步数。

The first line of input contains the number of test cases c (1<=c<=100). Each test case consists of two integers a,b (0<=a+b<=500000).

For each test case output the minimal number of swaps required to transpose an 2 $ ^{a} $ x2 $ ^{b} $ array. As it can be quite large, you have to output its remainder when divided by 1000003 (yes, it's a prime number :).

3
1 1
2 2
5 7

1
6
3744