Задача Период

Описание

При решении некоторых задач по информатике бывает полезно использовать такое свойство последовательности последних цифр степеней чисел как периодичность. Рассмотрим, например, последовательность степеней числа 2: 2 ⁰ = 1, 2 ¹ = 2, 2 ² = 4, 2 ³ = 8, 2 ⁴ = 16, 2 ⁵ = 32, . . . .

Последние цифры этих чисел образуют такую последовательность: 1, 2, 4, 8, 6, 2, 4, 8, . . . . Видно, что эта последовательность периодична с периодом 4 — второй ее элемент равен шестому, десятому, . . . , третий — седьмому, одиннадцатому, . . . , четвертый — восьмому, двенадцатому, . . . , пятый — девятому, тринадцатому, . . . .

Ваша задача состоит в том, чтобы найти период последовательности последних цифр степеней числа n в системе счисления с основанием k.

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

Первая строка входного файла содержит целое число n (2 ≤ n ≤ 10 ⁹ ). Вторая строка входного файла содержит целое число k (2 ≤ k ≤ 36). Оба числа заданы в десятичной системе счисления.

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

В выходной файл выведите длину периода рассматриваемой последовательности или -1, если эта последовательность не является периодичной.