요세푸스, 한 번 더!

프로 드링커 상근이는 술을 마실 때 요세푸스 문제와 똑같은 순서로 마신다. 요세푸스 문제를 천 번 넘게 풀어 본 상근이는 마지막에 술을 마시는 사람의 위치를 머릿속으로 계산할 수 있다. 그래서 함께 마시는 친구들은 상근이를 이기기 위해 새로운 순서를 제안했다.

먼저 모두 원탁에 둘러앉는다. 총 $N$명이 앉으면 각 사람의 번호는 $0$번부터 $N-1$번까지가 된다.

기존 요세푸스 문제와 달리, 다음 사람을 고를 때 두 정수 $a$와 $b$를 사용한다. 현재 지목된 사람의 번호가 $x$이면, 다음 사람의 번호는 $(a x^2 + b) \bmod N$이다.

가장 먼저 지목되는 사람은 $0$번이고, 그 다음부터는 위 식으로 차례차례 고른다.

각 사람은 기회를 한 번 더 받는다. 즉, 한 번 지목되면 술을 마시지 않고, 두 번째로 지목됐을 때 비로소 술을 마신다.

만약 어떤 사람이 세 번째로 지목되면, 그 즉시 모두 자리를 박차고 일어나 집으로 간다.

$N$과 $a$, $b$가 주어졌을 때, 술을 마시지 않고 집으로 가는 사람의 수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 세 정수 $N$, $a$, $b$가 공백으로 구분되어 주어진다. ($2 \le N \le 10^9$, $0 \le a, b < N$) 또한 첫 번째 사람이 술을 마시기까지 필요한 단계의 수는 $10^6$보다 작다. 입력의 마지막 줄에는 $0$이 하나 주어진다.

각 테스트 케이스마다 술을 마시지 않고 집으로 가는 사람의 수를 한 줄에 하나씩 출력한다.

이 문제는 사람들이 원형으로 둘러앉아 정해진 규칙에 따라 한 명씩 지목되는 고전 요세푸스 문제의 변형이다.