TRANSP - Transposing is Fun

Suppose you are given a 2a x 2b 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 2a x 2b 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

Added by:gawry
Date:2005-09-03
Time limit:27.97s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET

hide comments
2021-07-02 15:47:10
Nice Polya problem :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.