描述

弗拉维奥·约瑟夫斯（Flavius Josephus）曾经和他的战友们一起被困在一个洞穴里，被罗马人包围。约瑟夫斯的所有战友都宁愿自杀也不愿投降。于是他们围成一个圈，并商定了一个数字 $k$。接着，圆圈中每第 $k$ 个人就会自杀。然而，约瑟夫斯有不同的想法，他还不想死。根据传说，他成功地在圆圈中找到了一个安全的位置，使他成为最后一个应该自杀的人。他向罗马人投降，几年后成为了罗马公民。

鲜为人知的是，约瑟夫斯和他战友们的灵魂在现代都得以重生。显然，约瑟夫斯和他重生的战友们希望在未来避免类似的惨败。于是他们请了一家咨询公司来制定一个更好的决策方案。该公司提出了以下方案：

1. 为了遵循传统，所有士兵都应该站成一个圈。这样，每个士兵都会被分配一个介于 0 到 $N - 1$ 之间的数字，其中 $N$ 是士兵的数量。
2. 由于在旧方案中更改数字被证明效率极低，所以分配给一个士兵的数字在整个游戏过程中都不会改变。
3. 咨询公司会提供两个数字 $a$ 和 $b$，用于按如下方式计算下一个士兵的编号：设当前士兵的编号为 $x$，那么下一个士兵的编号就是 $a \cdot x^{2} + b \bmod N$ 的余数。
4. 我们从编号为 0 的士兵开始，每个士兵都根据上述公式计算下一个士兵的编号。
5. 因为每个人都应该有第二次机会，所以当一个士兵的编号第二次被计算出来时，他就会自杀。
6. 如果一个士兵的编号第三次被计算出来，游戏就会结束，所有剩下的士兵都会投降。

你需要编写一个程序，给定士兵的数量 $N$ 以及常数 $a$ 和 $b$，确定幸存者的数量。

输入

输入文件由几个测试用例组成。每个测试用例由一行包含三个整数 $N$（$2 \leq N \leq 10^{9}$）、$a$ 和 $b$（$0 \leq a, b < N$）的内容组成，这些整数之间用空格分隔。你可以放心地假设，第一个士兵在不超过一百万（$10^{6}$）步之后就会死亡。输入以一个单独的数字 0 结束，这个 0 不应被处理。

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

输出

对于每个测试用例，输出一行包含幸存者数量的内容。

0
2
4
96
698177783
999999994

来源

2006 年乌尔姆大学本地竞赛