#P2820. YY的GCD

    ID: 1912 传统题 2000ms 512MiB 尝试: 2895 已通过: 936 难度: 7 上传者: 标签>CF2200提高+/省选-莫比乌斯反演交换求和顺序线性筛一维前缀和整除分块

YY的GCD

YY的GCD

题目描述

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

给定 N,MN, M,求 1≤x≤N1 \leq x \leq N,1≤y≤M1 \leq y \leq M 且 gcd⁡(x,y)\gcd(x, y) 为质数的 (x,y)(x, y) 有多少对。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

2
10 10
100 100

样例输出 #1

30
2791

提示

T=104T = 10^4,N,M≤107N, M \leq 10^7。