← 返回题目列表

Codeforces · 1967/B1

B1. 反转卡(简单版)

中文机器翻译题面 查看原题

两个版本是不同的问题。您可能想阅读这两个版本。只有两个版本都解决了,你才能进行黑客攻击。

给你两个正整数 $$$n$$$, $$$m$$$。

计算满足以下条件的有序对 $$$(a, b)$$$ 的数量:

- $$$1\le a\le n$$$, $$$1\le b\le m$$$;
- $$$a+b$$$ 是 $$$b \cdot \gcd(a,b)$$$ 的倍数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1\le n,m\le 2 \cdot 10^6$$$)。

保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和都不超过 $$$2 \cdot 10^6$$$。

输出

对于每个测试用例,打印一个整数:有效对的数量。

示例

输入 #1

6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141

输出 #1

1
3
4
14
153
1643498

注意

在第一个测试用例中,只有 $$$(1,1)$$$ 满足条件。

在第四个测试用例中,$$$(1,1),(2,1),(2,2),(3,1),(4,1),(5,1),(6,1),(6,2),(6,3),(7,1),(8,1),(9,1),(10,1),(10,2)$$$满足条件。