LCMSUM2

Problem Description

There are $T$ queries. Each query gives two numbers $n, m$; compute $\left(\sum_{i=1}^n \sum_{j=1}^m [i, j]\right) \bmod 2^{60}$, where $[i, j]$ denotes the least common multiple of $i$ and $j$.

Input Format

The first line contains one integer $T$.

Each of the next $T$ lines contains two integers $n, m$.

Output Format

Output $T$ lines, each containing one number: the answer.

Sample Input

3
100 200
1000 2000
1000000 2000000

Sample Output

73830168
731817128790
282228897746124034

Constraints

For all test cases, $1 \le T \le 1000$ and $1 \le n, m \le 10^7$.