D. Удачные цепочки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем пару положительных целых чисел $$$(x, y)$$$ удачной, если их наибольший общий делитель равен $$$1$$$ ($$$\gcd(x, y) = 1$$$)

Назовем цепочкой, порожденной $$$(x, y)$$$, последовательность пар $$$(x, y)$$$, $$$(x + 1, y + 1)$$$, $$$(x + 2, y + 2)$$$, $$$\dots$$$, $$$(x + k, y + k)$$$ для некоторого целого $$$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$$$, если цепочка может быть бесконечно длинной.

Пример
Входные данные
4
5 15
13 37
8 9
10009 20000
Выходные данные
0
1
-1
79
Примечание

В первом наборе входных данных $$$\gcd(5, 15) = 5 > 1$$$, то есть данная пара не является удачной, а потому длина удачной цепочки равна $$$0$$$.

Во втором наборе входных данных $$$\gcd(13 + 1, 37 + 1) = \gcd(14, 38) = 2$$$. А потому удачная цепочка состоит из одной пары $$$(13, 37)$$$.