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.