← 返回题目列表

Codeforces · 1766/D

D. 幸运链

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

让我们命名一对正整数 $$$(x, y)$$$ 幸运的是,如果它们的最大公约数等于 $$$1$$$ ($$$\gcd(x, y) = 1$$$)。

Let's define a chain induced by $$$(x, y)$$$ as a sequence of pairs $$$(x, y)$$$, $$$(x + 1, y + 1)$$$, $$$(x + 2, y + 2)$$$, $$$\dots$$$, $$$(x + k, y + k)$$$ for some integer $$$k \ge 0$$$.链的长度是它所包含的对的数量,或者$$$(k + 1)$$$。

如果链中的所有对都是幸运的,那么我们将这样的链命名为“幸运”。

给你 $$$n$$$ 对 $$$(x_i, y_i)$$$。计算每对由该对引起的最长幸运链的长度。请注意,如果 $$$(x_i, y_i)$$$ 本身不幸运,则该链的长度将为 $$$0$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 对的数量。

接下来的 $$$n$$$ 行包含 $$$n$$$ 对 — 每行一个。第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i < y_i \le 10^7$$$) — 对应的对。

输出

打印 $$$n$$$ 整数,其中第 $$$i$$$ 整数是由 $$$(x_i, y_i)$$$ 或 $$$-1$$$ 引起的最长幸运链的长度(如果该链可以无限长)。

示例

输入 #1

4
5 15
13 37
8 9
10009 20000

输出 #1

0
1
-1
79

注意

第一个测试用例中,$$$\gcd(5, 15) = 5 > 1$$$,所以已经不幸运了,所以幸运链的长度为$$$0$$$。

在第二个测试用例中,$$$\gcd(13 + 1, 37 + 1) = \gcd(14, 38) = 2$$$。因此,幸运链由一对 $$$(13, 37)$$$ 组成。