힐베르트 해시브라운

힐베르트 호텔에는 0번, 1번, 2번, ... 으로 번호가 붙은 방이 무한히 많다. 그래서 모든 방이 찬 것처럼 보여도 손님 한 명을 더 받을 수 있다. $i$번 방 손님을 모두 $i+1$번 방으로 옮기면 0번 방이 비기 때문이다. 호텔에 딸린 식당 힐베르트 해시브라운의 식탁은 무한하지 않다. 아주 많기는 하지만 개수가 정해져 있다.

게다가 이 식당의 종업원은 몹시 게으르다. 어느 식탁이 비었는지 기록해 두는 대신, 손님이 오면 간단한 공식 하나로 자리를 정한다. 손님에게 호텔 방 번호 $x$를 묻고, 그 번호를 $p$제곱한 뒤 $q$를 더한다. 이렇게 하면 수가 아주 커지고 식탁은 $n$개뿐이므로, 종업원은 $n$으로 나눈 나머지를 구해 그 번호의 식탁으로 손님을 안내한다. 식탁 번호는 0번부터 $n-1$번까지이고, 손님이 가는 자리는 $(x^p + q) \bmod n$번 식탁이다. 그 식탁에 이미 다른 손님이 앉아 있으면 온 손님은 아무것도 먹지 못하고 돌아간다.

종업원은 날마다 $p$와 $q$를 새로 고른다. 그러다 어떤 날에는 손님이 아무리 많이 와도 끝내 쓰이지 않는 식탁이 있다는 사실을 알아차렸다. 예를 들어 $n = 3$, $p = 2$, $q = 1$이면 0번 식탁은 절대 쓰이지 않는다. $x^2 + 1 \equiv 0 \pmod 3$을 만족하는 정수 $x$가 없기 때문이다.

방 번호는 0 이상의 모든 정수이다. $p$, $q$, $n$이 주어질 때 손님이 앉을 수 있는 식탁이 최대 몇 개인지 구하시오.

첫째 줄에 세 정수 $p$, $q$, $n$이 공백으로 구분되어 주어진다. ($1 \le p < 2^{31}$, $0 \le q < 2^{31}$, $2 \le n < 2^{31}$)

쓰일 수 있는 식탁의 최대 개수를 출력한다.