512008 - 转置

【题目描述】转置（trans）

一个2a×2b的矩阵，在内存中的存放方式是先存第一行的，再存第二行的…每行也是从左到右存放。现在你想把它变成它的转置矩阵（a transposed matrix，也是一样的储存方式），但是只能用交换操作（即交换两个储存单元的内容），问至少需要交换多少步？

第一行一个整数T(1≤T≤400000)表示测试用例组数。 接下来有T行，每行一组测试数据为两个整数a和b（0≤a+b≤1000000）。

对每组数据输出一个整数，即转置矩阵需要的最少交换次数。因为这个次数可能很大，你只需要输出它模1000003的值（1000003是素数）。