#P2257. YY的GCD

YY的GCD

题目描述

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

给定 N,MN, M,求 1xN1 \leq x \leq N1yM1 \leq y \leq Mgcd(x,y)\gcd(x, y) 为质数的 (x,y)(x, y) 有多少对。

输入格式

第一行一个整数 TT 表述数据组数。

接下来 TT 行,每行两个正整数,N,MN, M

输出格式

TT 行,每行一个整数表示第 ii 组数据的结果。

2
10 10
100 100
30
2791

提示

T=104T = 10^4N,M107N, M \leq 10^7