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

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.

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.