Sum of GCDs

Problem Description

$T$ queries. Each query gives two numbers $n, m$; compute $\sum_{i=1}^n \sum_{j=1}^m (i, j)$, where $(i, j)$ denotes $\gcd(i, j)$.

Input Format

The first line contains an integer $T$.

The next $T$ lines each contain two integers $n, m$.

Output Format

A total of $T$ lines, each containing one number: the answer.

Sample Input

3
100 200
1000 2000
1000000 2000000

Sample Output

63542
9067212
17457854316166

Constraints

For all data, $1\leq T\leq 1000$ and $1\leq n, m \leq 10^7$ are guaranteed.