Назовем пару положительных целых чисел $$$(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)$$$.
