github.com/captn3m0/codechef.git

---
{"languages_supported":{"0":"NA"},"title":"LCM","category":"NA","old_version":true,"problem_code":"LCM","tags":{"0":"NA"},"layout":"problem"}
---

<h3> All submissions for this problem are available. </h3><p>Given A and B, compute the sum of lcm(a, b) over all pairs of positive integers a and b such that:

</p><p>(1)  a&lt;=A and b&lt;=B. <br />
(2) There is no integer n&gt;1 such that n<sup>2</sup> divides both a and b. 

</p><p>Give your answer modulo 2<sup>30</sup>.

<h3>Input</h3>
</p><p>The 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&lt;=A, B&lt;=4000000).

<h3>Output</h3>
</p><p>Print the answer to each test case on a separate line.

<h3>Example</h3>

<pre>
<b>Input:</b>

4
2 4
3 3
6 5
8 3

<b>Output:</b>

24
28
233
178
</pre></p>