Suppose you are given a 2^a x 2^b array. It is stored sequentially in memory in the usual way, first values in the first row, then values in the second one and so on. You would like to transpose it, but you don't have any additional memory. The only operation that you can perform is swapping contents of two memory cells. What is the minimal number of such operations required for transposition?

Input

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).

Output

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

Example

Input:
3
1 1
2 2
5 7

Output:
1
6
3744