Josephus, Once More!

Time limit2sMemory limit128 MB

Summary

People are selected around a circle by the rule f(x)=(a x^2+b) mod N, starting at 0; each drinks on the second selection, and on the third everyone leaves. Count how many never drink.

Level: Medium7 of 10
Topics: Simulation, Math, Implementation
Solved: No attempts yet

Problem

Sanggeun, a pro drinker, drinks in exactly the same order as the Josephus problem. Having solved the Josephus problem more than a thousand times, he can figure out in his head who drinks last. So his drinking buddies came up with a new order to beat him.

First, everyone sits around a round table. If $N$ people sit down, they are numbered from $0$ to $N-1$ .

Unlike the classic Josephus problem, the next person is chosen using two integers $a$ and $b$ . If the currently selected person is numbered $x$ , the next person is numbered $(a x^2 + b) \bmod N$ .

The very first person selected is number $0$ , and every subsequent person is chosen with the formula above.

Each person gets one extra chance. That is, being selected once does not mean drinking; a person drinks only when selected for the second time.

If a person is selected for the third time, everyone immediately jumps up and goes home.

Given $N$ , $a$ , and $b$ , write a program that finds how many people go home without drinking.

Input

The input consists of several test cases. Each test case is a single line containing three integers $N$ , $a$ , and $b$ separated by spaces. ( $2 \le N \le 10^9$ , $0 \le a, b < N$ ) Also, the number of steps needed for the first person to drink is less than $10^6$ . The last line of the input contains a single $0$ .

Output

For each test case, print the number of people who go home without drinking, one per line.

Hint

This is a variation of the classic Josephus problem, where people sit in a circle and are selected one by one according to a fixed counting rule.

Examples5

Example 1

Input

2 1 1
5 1 1
10 3 7
101 9 2
698253463 1 181945480
1000000000 999999999 999999999
0

Expected output

Example 2
Input
```
2 0 0
0
```
Expected output
```
1
```
Example 3
Input
```
2 0 1
0
```
Expected output
```
1
```
Example 4
Input
```
3 1 1
0
```
Expected output
```
2
```
Example 5
Input
```
2 0 0
3 1 1
4 1 1
0
```
Expected output
```
1
2
2
```