YY的GCD

题目描述

神犇 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$ 组数据的结果。

输入输出样例

输入样例 #1

2
10 10
100 100

输出样例 #1

30
2791

说明

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