Задача 26. Манит карусель ≡

Условие

...

Манит, манит, манит карусель

В путешествие по замкнутому кругу.

Дарит, дарит, дарит карусель

То надежду, то досадную разлуку.

...

Регина Лисиц, "Карусель", 1996 г.

В детском парке открылся новый аттракцион "Карусель" на n мест. Согласно технике безопасности при её эксплуатации рассаживать детей можно только таким образом, чтобы центр тяжести всех катающихся совпадал с центром карусели и расстояния между ними по окружности были одинаковыми. Например, при n = 6 одновременно могут кататься 2, 3 или 6 ребят, а при n = 5 — только ровно 5. Другими словами, разрешается запустить карусель, если на ней размещено k детей, причём k — делитель n и k ≠ 1.

В очереди к карусели стоит d детей. Дети, которые покатались на карусели, уходят в поисках новых развлечений. Какое минимальное количество запусков аттракциона следует осуществить, чтобы все дети прокатились на карусели ровно по одному разу?

Формат входных данных

Две строки входных данных содержат натуральные числа n и d.

Формат выходных данных

Выведите одно натуральное число — ответ к задаче. Если всех ребят прокатить не получится, выведите -1.

Ограничения

1 ≤ n, d ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В первом примере дано n = 16 и d = 14 (карусель на 16 мест, в очереди 14 детей). Достаточно 3 запуска карусели: в первый раз прокатятся 8 ребят, во второй — 4, в третий — 2.

Во втором примере дано n = 15 и d = 7. Всех детей прокатить не получится, так как согласно правилам разрешено катать только по 3, 5 или 15 ребят.

Примеры тестов

16
14

3

15
7

-1