Sequence-2

Vasylko is exploring sequences and has recently learned about exponentiation. Inspired by this, he has devised a new sequence.

He starts by writing a natural number (A) on the board. Each subsequent number in the sequence is obtained by raising (A) to the power of the previous number. Thus, the sequence is defined as follows:

[ x[1] = A ]

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

Vasylko's goal is to find the first element in this sequence that is divisible by a given number (N). Due to the potentially large size of these numbers, he needs your assistance.

Input

You are given two natural numbers (A) and (N) ((1 $\le$ A $\le$ 10^9), (1 $\le$ N $\le$ 10^9)).

Output

If no element in the sequence is divisible by (N), output (0). Otherwise, output the smallest index of the sequence element that is divisible by (N).

Examples