{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003eGiven A and B, compute the sum of lcm(a, b) over all pairs of positive integers a and b such that:\n\n\u003c/p\u003e\u003cp\u003e(1) a\u003c\u003dA and b\u003c\u003dB. \u003cbr /\u003e\n(2) There is no integer n\u003e1 such that n\u003csup\u003e2\u003c/sup\u003e divides both a and b. \n\n\u003c/p\u003e\u003cp\u003eGive your answer modulo 2\u003csup\u003e30\u003c/sup\u003e.\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003c/p\u003e\u003cp\u003eThe first line contains the number of test cases, t (about 200). Each of the next t lines contains two space-separated integers A and B (1\u003c\u003dA, B\u003c\u003d4000000).\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003c/p\u003e\u003cp\u003ePrint the answer to each test case on a separate line.\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\n\u003cpre\u003e\n\u003cb\u003eInput:\u003c/b\u003e\n\n4\n2 4\n3 3\n6 5\n8 3\n\n\u003cb\u003eOutput:\u003c/b\u003e\n\n24\n28\n233\n178\n\u003c/pre\u003e\u003c/p\u003e"}}]}