让我们命名一对正整数 $$$(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)$$$ 组成。