{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003ch3\u003eProblem\u003c/h3\u003e\r\n\u003cp\u003e\r\nSuppose you are given a 2\u003cfont style\u003d\"vertical-align: super\"\u003ea\u003c/font\u003ex2\u003cfont style\u003d\"vertical-align: super\"\u003eb\u003c/font\u003e 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\u0027t 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?\r\n\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\nFirst line of input contains number of test cases c (1\u0026lt;\u003dc\u0026lt;\u003d400000). Each test case consists of two integers a, b (0\u0026lt;\u003da+b\u0026lt;\u003d1000000).\r\n\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\nFor each test case output minimal number of swaps required to transpose an 2\u003cfont style\u003d\"vertical-align: super\"\u003ea\u003c/font\u003ex2\u003cfont style\u003d\"vertical-align: super\"\u003eb\u003c/font\u003e array. As it can be quite large, you have to output its remainder when divided by 1000003 (yes, it\u0027s a prime number :).\r\n\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\r\nInput:\r\n3\r\n1 1\r\n2 2\r\n5 7\r\n\r\nOutput:\r\n1\r\n6\r\n3744\u003c/pre\u003e\r\n\n\u003c/div\u003e"}}]}