说明

hhc 最近在玩一款游戏

这款游戏中，玩家们要扮演海盗在海上打捞发掘宝藏，每次出发需要凑足 $n$ 个玩家，以入队顺序编号分别为 $1 \sim n$

在找到宝藏以后，玩家们需要进行一轮 "内战" 来让自己获得更多的宝藏

"内战" 的规则是这样的：

所有人站成一圈，每回合所有玩家会同时向自己顺时针方向的下一个玩家进行一次攻击

对于两个编号为 $x,y$ 的玩家，如果这一回合游戏是 $x$ 向 $y$ 发动攻击，若 $x,y$ 的最大公约数不为 $1$，则认为此次攻击有效，那么 $y$ 将出局

当然，如果是三个玩家 $x,y,z$ 排成一圈，这一回合游戏满足 $gcd(y,z) != 1$ 并且 $gcd(z,x) != 1$ ，那么这一轮 $x$ 和 $y$ 均会出局

显然 "内战" 在一定回合以后就会停下，此时剩下的玩家无法再发动有效的攻击，此时剩下的所有玩家将均分宝藏

现在 hhc 想知道，如果已经知道 $n$ 个玩家一开始的站位，能有多少个玩家留到最后均分宝藏？

输入格式

第一行 $n,m,K$，其中 $n$ 是人数,$m,K$ 为生成初始站位的参数

这 $n$ 个人的初始站位由以下代码生成,生成的 $a[i]$ 即为第 $i$ 个人的编号

```cpp
// 请注意生成函数中的所有类型必须为 int
int K;
int get_number(){
K = K * 214013 + 2531011;
return (abs(K)) % n + 1;
}

for (int i = 1; i <= n; ++i){
a[i] = i;
}
for (int i = 1; i <= m; ++i){
x = get_number(), y = get_number();
swap(a[x], a[y]);
}
```

对于 $50\%$ 的数据：$n\leq 1000$。

对于 $80\%$ 的数据：$n\leq 10^5$。

对于 $100\%$ 的数据：$1\leq n\leq 10^6,m\leq 10^6,K$ 在 $int$ 范围内。

输出格式

输出一个整数，表示能留到最后的玩家个数

样例

6 0 0

6