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

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

• на нем есть два кодовых механизма, первый из которых изначально указывает на число $$$a$$$, а второй — на число $$$b$$$;
• первый кодовый механизм сломан, поэтому изменить значение $$$a$$$ нельзя;
• второй кодовый механизм можно вращать только в одном направлении, тем самым увеличивая значение $$$b$$$;
• замок открывается тогда и только тогда, когда существует целое число $$$d \gt 1$$$, делящее и $$$a$$$, и $$$b$$$ (иными словами, когда у $$$a$$$ и $$$b$$$ есть общий делитель больше единицы).

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

Все указанные ниже дополнительные ограничения выполняются для всех тестовых случаев тестов группы.