Последовательность-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.