Задачи
Последовательность-2
Последовательность-2
Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность.
Сначала он пишет на доске натуральное число \textbf{A}. Каждое следующее число, выписанное им на доске, будет равно степени с основанием \textbf{A} и показателем, равным предыдущему числу. Другими словами, последовательность будет выглядеть так:
\textbf{x\[1\]} = \textbf{A},
\textbf{x\[k + 1\]} = \textbf{A^x^\{\[\}^k^\{\]\}}, \textbf{k} > \textbf{0}
После этого он решил узнать элемент этой последовательности с минимальным номером, который бы делился на данное число \textbf{N}. Поскольку числа на доске могут быть довольно большими, без вашей помощи ему не обойтись.
\InputFile
Вводятся два натуральных числа \textbf{A}, \textbf{N} (\textbf{1} ≤ \textbf{A} ≤ \textbf{10^9},^\{ \}\textbf{1} ≤ \textbf{N} ≤ \textbf{10^9}).
\OutputFile
Если ни один элемент последовательности не делится на \textbf{N}, выведите \textbf{0}. Иначе выведите минимальный номер элемента рассмотренной последовательности, делящегося на \textbf{N}.
Входные данные #1
2 2
Выходные данные #1
1