Послідовність-2#582
Василь продовжує створювати послідовності. Сьогодні в школі він дізнався про операцію піднесення до степеня і вирішив придумати нову послідовність.
Спочатку він записує на дошці натуральне число . Кожне наступне число, яке він записує, дорівнює , піднесеному до степеня попереднього числа. Інакше кажучи, послідовність визначається наступним чином:
Далі Василь хоче знайти елемент цієї послідовності з найменшим індексом, який ділиться на задане число . Оскільки числа в послідовності можуть ставати дуже великими, йому потрібна ваша допомога.
Задано два натуральних числа , (1 \leq A \leq 10^9, 1 \leq N \leq 10^9).
Якщо в послідовності немає елемента, що ділиться на , виведіть . Інакше виведіть найменший індекс першого елемента, що ділиться на .
Приклад 1