Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность.

   Сначала он пишет на доске натуральное число A. Каждое следующее число, выписанное им на доске, будет равно степени с основанием A и показателем, равным предыдущему числу. Другими словами, последовательность будет выглядеть так:

x[1] = A,

x[k + 1] = A^x[k], k > 0

   После этого он решил узнать элемент этой последовательности с минимальным номером, который бы делился на данное число N. Поскольку числа на доске могут быть довольно большими, без вашей помощи ему не обойтись.

   Входные данные

   Вводятся два натуральных числа A, N (1 ≤ A ≤ 10⁹, 1 ≤ N ≤ 10⁹).

   Выходные данные

   Если ни один элемент последовательности не делится на N, выведите 0. Иначе выведите минимальный номер элемента рассмотренной последовательности, делящегося на N.