Hilbert's Hash Browns

Hilbert's Hotel has infinitely many rooms, numbered 0, 1, 2, and so on, so it takes in one more guest even when it looks full: every guest in room $i$ moves to room $i+1$, and room 0 becomes free. The restaurant attached to the hotel, Hilbert's Hash Browns, is not infinite. It has a very large number of tables, but that number is fixed.

The waiter there is very lazy. Instead of keeping a record of which tables are free, he seats every customer with one simple formula. He asks the customer for the hotel room number $x$, raises that number to the power $p$, and adds $q$. The result is huge and there are only $n$ tables, so he takes the remainder modulo $n$ and points the customer to that table. Tables are numbered 0 to $n-1$, and the customer goes to table $(x^p + q) \bmod n$. If someone already sits there, the customer leaves hungry.

The waiter picks new values of $p$ and $q$ every day, and he has noticed that on some days a table is never used however many customers arrive. With $n = 3$, $p = 2$ and $q = 1$, table 0 is never used, because no integer $x$ satisfies $x^2 + 1 \equiv 0 \pmod 3$.

Room numbers run over every nonnegative integer. Given $p$, $q$ and $n$, find the largest number of tables that can be used.

The first line contains three integers $p$, $q$ and $n$ separated by spaces ($1 \le p < 2^{31}$, $0 \le q < 2^{31}$, $2 \le n < 2^{31}$).

Print the largest number of tables that can be used.