Назовем пару положительных целых чисел \((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\) чисел, где \(i\)-е число означает максимальную длину удачной цепочки, порожденной парой \((x_i, y_i)\) или \(-1\), если цепочка может быть бесконечно длинной.
Примечание
В первом наборе входных данных \(\gcd(5, 15) = 5 > 1\), то есть данная пара не является удачной, а потому длина удачной цепочки равна \(0\).
Во втором наборе входных данных \(\gcd(13 + 1, 37 + 1) = \gcd(14, 38) = 2\). А потому удачная цепочка состоит из одной пары \((13, 37)\).