Задача: Эрен и подвал

Эрен хочет открыть подвал своего дома, но, к сожалению, потерял ключ. Альтернативный способ попасть в подвал — ввести на замке разблокирующий его код доступа.

Замок на двери подвала устроен следующим образом:

• на нем есть два кодовых механизма, первый из которых изначально указывает на число \(a\), а второй — на число \(b\);

• первый кодовый механизм сломан, поэтому изменить значение \(a\) нельзя;

• второй кодовый механизм можно вращать только в одном направлении, тем самым увеличивая значение \(b\);

• замок открывается тогда и только тогда, когда существует целое число \(d > 1\), делящее и \(a\), и \(b\) (иными словами, когда у \(a\) и \(b\) есть общий делитель больше единицы).

За одну секунду Эрен может повернуть второй кодовый механизм так, что \(b\) увеличится ровно на \(1\). Определите, за какое минимальное время Эрен сможет открыть подвал.

Формат входных данных
В первой строке дано единственное целое число \(t\) — количество тестовых случаев \((1 \leqslant t \leqslant 1000)\).

В \(i\)-й из следующих \(t\) строк через пробел даны два целых числа \(a_i\) и \(b_i\) — начальные значения, на которые указывают кодовые механизмы в \(i\)-м тесте (\(2 \leqslant a_i, b_i \leqslant 10^9\)).

Формат выходных данных
Для каждого теста выведите в отдельной строке минимальное время, за которое Эрен откроет подвал.

Ваш ответ: