Problem

Suppose you are given a 2ax2b 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 minimal number of such operations required for transposition?

Input

First line of input contains number of test cases c (1<=c<=400000). Each test case consists of two integers a, b (0<=a+b<=1000000).

Output

For each test case output minimal number of swaps required to transpose an 2ax2b 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