题目描述

神犇 YY 虐完数论后给傻× kAc 出了一题

给定 $N, M$，求 $1 \leq x \leq N$，$1 \leq y \leq M$ 且 $\gcd(x, y)$ 为质数的 $(x, y)$ 有多少对。

输入格式

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

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

输出格式

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

2
10 10
100 100

30
2791

提示

$T = 10^4$，$N, M \leq 10^7$。