Coprime Pairs

Problem Description

There are $T$ queries. Each query gives two numbers $n, m$; find the number of pairs $(i, j)$ such that $1 \leq i \leq n$, $1 \leq j \leq m$ and $i, j$ are coprime.

Input Format

The first line contains an integer $T$. The following $T$ lines each contain 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

12203
1216677
1215854454422

Constraints

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