TRANSP2 - Transposing is Even More Fun
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 transpostion?
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).
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 :).
Input: 3 1 1 2 2 5 7 Output: 1 6 3744