Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

number theory

*1600

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Lucky Chains

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputLet'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

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

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.

Example

Input

4 5 15 13 37 8 9 10009 20000

Output

0 1 -1 79

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 08:27:59 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|