Divisibility Preservation in Base Conversion Algorithm

Consider the following algorithm defined in base \(b\) with a modulus \(p\) (not necessarily prime). For any positive integer \(N\) (represented in base \(b\)), we perform the following steps:

1. Partition the base-\(b\) representation of \(N\) into segments of \(k\) consecutive digits, starting from the least significant digit. (The highest segment may have fewer than \(k\) digits.)
2. Label the segments from 0 upward (with the segment containing the least significant digits being segment 0).
3. For each segment with index \(i\), let \(a_i\) be its value when interpreted in base \(b\). Then define an auxiliary value \(c_i\) as follows:
   • If \(i\) is even, choose the smallest nonnegative integer \(c_i\) such that \[ a_i - c_i \equiv 0 \pmod{p}. \] (In other words, \(c_i \equiv a_i \pmod{p}\).)
   • If \(i\) is odd, choose the smallest nonnegative integer \(c_i\) such that \[ a_i + c_i \equiv 0 \pmod{p}. \] (That is, \(c_i \equiv -a_i \pmod{p}\).)
4. Finally, construct a new number \(f(N)\) by concatenating the \(c_i\)'s, with the segment corresponding to the highest index forming the most significant digits and the segment with index 0 forming the least significant digits. All operations (including the concatenation) are performed in base \(b\).

It can be proved that for some choices of \(b\) and \(p\), no matter what positive integer \(N\) is chosen, \(N\) is divisible by \(p\) if and only if \(f(N)\) is divisible by \(p\). Moreover, the number of digits of \(f(N)\) is smaller than that of \(N\), so by applying this procedure repeatedly, one may eventually reduce to a small number and test divisibility easily.

For given integers \(b\) and \(p\), your task is to determine the smallest positive integer \(k\) (the group length in the first step) such that for every positive integer \(N\) (written in base \(b\)) the divisibility condition holds: \(N \equiv 0 \pmod{p}\) if and only if \(f(N) \equiv 0 \pmod{p}\). If no such \(k\) exists, output -1.

Formal Explanation:

If we denote \(N = \sum_{i=0}^{m-1} a_i\, b^{i\cdot k}\) (where the groups \(a_i\) are formed as described) and \(f(N) = \sum_{i=0}^{m-1} d_i\, b^{i}\), with

[ d_i = \begin{cases} a_i \pmod{p} & \text{if } i \text{ is even},\ -a_i \pmod{p} & \text{if } i \text{ is odd}, \end{cases} ]

then, by linearity, the condition holds for all choices of digits (a_i) if and only if for every (i\ge 0):

[ b^{i\cdot k} \equiv (-1)^i, b^{i} \pmod{p}. ]

Assuming (b) is invertible modulo (p) (i.e. (p \nmid b)), canceling (b^i) yields the necessary and sufficient condition

[ b^{k-1} \equiv -1 \pmod{p}. ]

If (p) divides (b) then it can be verified that the condition holds for every positive integer (k) (so in this case the answer is (1)). In all other cases, you must find the least positive (k) satisfying the above congruence or report ( -1 ) if none exists.

inputFormat

The input consists of a single line containing two space-separated integers \(b\) and \(p\) \((2 \le b \le 10^9,\ 1 \le p \le 10^9)\). It is guaranteed that \(p\) is positive.

outputFormat

Output a single integer representing the smallest positive integer \(k\) that works, or -1 if no such \(k\) exists.

sample

14 9

4