Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность. Сначала он пишет на доске натуральное число \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}.