Послідовність-2
Василько продовжує конструювати послідовності. Сьогодні в школі його познайомили з операцією піднесення до степеню, і Василько придумав нову послідовність.
Спочатку він пише на дошці натуральне число A. Кожне наступне число, записане ним на дошці, буде дорівнювати степені з основою A і показником, рівним попередньому числу. Іншими словами, послідовність буде виглядати так:
x[1] = A,
x[k + 1] = A^x^{[}^k^{]}, k > 0
Після цього він вирішив взнати елемент цієї послідовності з мінімальним номером, який би ділився на задане число N. Оскільки числа на дошці можут бути досить великими, без вашої допомоги йому не обійтись.
Вхідні дані
Вводяться два натуральних числа A, N (1 ≤ A ≤ 10^9,^{ }1 ≤ N ≤ 10^9).
Вихідні дані
Якщо дожен елемент послідовності не ділиться на N, виведіть 0. Інакше виведіть мінімальний номер елемента разглянутої послідовності, який ділиться на N.