Lucky Chains
Contest: Educational Codeforces Round 139 (Rated for Div. 2)
Difficulty rating: 1600
Tags: math, number theory

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$$$.

Input format:
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 < y_i \le 10^7$$$) — the corresponding pair.

Output format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, $$$\gcd(5, 15) = 5 > 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)$$$.

Example input:
4
5 15
13 37
8 9
10009 20000

Example output:
0
1
-1
79

Editorial:
Suppose, $$$\gcd(x + k, y + k) = g$$$. It means that $$$(y + k) - (x + k) = (y - x)$$$ is also divisible by $$$g$$$, or $$$\gcd(x + k, y - x) = h$$$ is divisible by $$$g$$$. And backward: if $$$\gcd(x + k, y - x) = h$$$, then $$$(x + k) + (y - x) = (y + k)$$$ is also divisible by $$$h$$$, or $$$\gcd(x + k, y + k) = g$$$ is divisible by $$$h$$$.
Since $$$h$$$ is divisible by $$$g$$$ and $$$g$$$ is divisible by $$$h$$$, so $$$h = g$$$. In other words, we proved that $$$\gcd(x + k, y + k) = \gcd(x + k, y - x)$$$.
Now, knowing the equivalence above, we can understand that we are looking for the smallest $$$k \ge 0$$$ such that $$$\gcd(x + k, y - x) > 1$$$. In other words, we are searching $$$k$$$ such that $$$x + k$$$ is divisible by some $$$d > 1$$$, where $$$d$$$ is some divisor of $$$(y - x)$$$.
The problem is that there are a handful of divisors for some $$$(y - x)$$$. But we can note that we can consider only prime divisors of $$$(y - x)$$$: if $$$d | (y - x)$$$ and $$$d$$$ is composite then there is some prime $$$p | d$$$, thus $$$p | (y - x)$$$.
It's easy to prove that there are no more than $$$\log_2{n}$$$ prime divisors of some $$$n$$$. Now the question is how to find all these prime divisors.
Note that if you know only one prime divisor for each value from $$$1$$$ to $$$n$$$, then you can find all prime divisors for all $$$k \le n$$$ in $$$O(\log{k})$$$. The prime divisors $$$p_i$$$ are next:
• $$$p_1 = minD[k]$$$, $$$k_1 = \frac{k}{minD[k]}$$$;
• $$$p_2 = minD[k_1]$$$, $$$k_2 = \frac{k_1}{minD[k_1]}$$$;
• $$$p_3 = minD[k_2]$$$, $$$k_3 = \frac{k_2}{minD[k_2]}$$$;
• and so on until $$$k_i > 1$$$.
The final step is to calculate a prime divisor $$$minD[i]$$$ for each value from $$$1$$$ to $$$A$$$, where $$$A \ge \max(y_i)$$$ or $$$A \ge 10^7$$$. We can do it by slight modifications of Sieve of Eratosthenes: at the step, where you have some prime $$$p$$$ and want to "throw out" all values $$$k \cdot p$$$, set $$$minD[kp] = p$$$ for each $$$kp$$$ (plus set $$$minD[p] = p$$$).
As a result, we, firstly, calculate Sieve in $$$O(N \log{\log{N}})$$$ and, secondly, calculate answer for each pair $$$(x_i, y_i)$$$ in $$$O(\log{N})$$$.
Note that the input and output is large, so you should you tricks to speed up your input and output.