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