CF1766D.Lucky Chains

Let's name a pair of positive integers $(x, y)$ lucky if the greatest common divisor of them is equal to $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$. The length of the chain is the number of pairs it consists of, or $(k + 1)$.

Let's name such chain lucky if all pairs in the chain are lucky.

You are given $n$ pairs $(x_i, y_i)$. Calculate for each pair the length of the longest lucky chain induced by this pair. Note that if $(x_i, y_i)$ is not lucky itself, the chain will have the length $0$.

我们称一对正整数 $(x, y)$ 为“幸运的”，当且仅当它们的最大公约数为 $1$（即 $\gcd(x, y) = 1$）。

我们定义由 $(x, y)$ 诱导出的一条链为如下形式的数对序列：$(x, y)$，$(x + 1, y + 1)$，$(x + 2, y + 2)$，$\dots$，$(x + k, y + k)$，其中 $k \ge 0$ 为某个整数。该链的长度为其所含数对的个数，即 $(k + 1)$。

若一条链中所有数对均为幸运的，则称该链为“幸运链”。

现给你 $n$ 对数 $(x_i, y_i)$。对每一对 $(x_i, y_i)$，请计算由其诱导出的最长幸运链的长度。注意：若 $(x_i, y_i)$ 本身不是幸运的，则对应链的长度为 $0$。

The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the number of pairs.

Next $n$ lines contains $n$ pairs — one per line. The $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i \lt y_i \le 10^7$) — the corresponding pair.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示数对的个数。

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

Print $n$ integers, where the $i$-th integer is the length of the longest lucky chain induced by $(x_i, y_i)$ or $-1$ if the chain can be infinitely long.

输出 $n$ 个整数，其中第 $i$ 个整数为由 $(x_i, y_i)$ 诱导的最长幸运链的长度；若该链可无限长，则输出 $-1$。

In the first test case, $\gcd(5, 15) = 5 \gt 1$, so it's already not lucky, so the length of the lucky chain is $0$.

In the second test case, $\gcd(13 + 1, 37 + 1) = \gcd(14, 38) = 2$. So, the lucky chain consists of the single pair $(13, 37)$.

在第一个测试用例中，$\gcd(5, 15) = 5 \gt 1$，因此它已经不是幸运的，故幸运链的长度为 $0$。

在第二个测试用例中，$\gcd(13 + 1, 37 + 1) = \gcd(14, 38) = 2$。因此，幸运链仅包含单个数对 $(13, 37)$。