Задача №114772. Эрен и подвал
Эрен хочет открыть подвал своего дома, но, к сожалению, потерял ключ. Альтернативный способ попасть в подвал — ввести на замке разблокирующий его код доступа.
Замок на двери подвала устроен следующим образом:
- на нем есть два кодовых механизма, первый из которых изначально указывает на число \(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\)).
Для каждого теста выведите в отдельной строке минимальное время, за которое Эрен откроет подвал.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
Все указанные ниже дополнительные ограничения выполняются для всех тестовых случаев тестов группы.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | \(t \leqslant 10\), \(a_i \leqslant 1000\), \(b_i \leqslant 100\) | полная | |
| 2 | 23 | \(t \leqslant 100\), \(a_i, b_i \leqslant 10000\) | 1 | полная |
| 3 | 25 | \(a_i\) — простое число | полная | |
| 4 | 42 | нет | 1 – 3 | первая ошибка |
3 15 7 23 11 35 42
2 12 0