题目描述

神犇 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$。