YY的GCD

神犇 YY 虐完数论后给傻 × kAc 出了一题：给定 $N, M$，求 $1\le x\le N$、$1\le y\le M$ 且 $\gcd(x, y)$ 为质数的 $(x, y)$ 有多少对。

kAc 这种傻 × 必然不会了，于是向你来请教。本题为多组输入。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个正整数，表示 $N, M$。

输出格式

输出 $T$ 行，每行一个整数，表示第 $i$ 组数据的结果。

样例输入

2
10 10
100 100

样例输出

30
2791

数据范围

• $T=10^4$；
• $N, M\le 10^7$。

来源与许可

本题题面与测试数据整理自 BZOJ 2820。

样例 1

输入

2
10 10
100 100

输出

30
2791