给定一个素数 $p$。
对于满足 $0 \le x < p$ 的整数 $x$，定义 $f(x)$ 为满足存在整数 $b$ 使得 $(a^2 + b^2) \pmod p = x$ 的最小非负整数 $a$。
你的目标是求出 $\max(f(0), f(1), \dots, f(p - 1))$。
可以证明，对于每个素数 $p$ 和每个整数 $x$，都能找到至少一对 $a, b$ 使得 $(a^2 + b^2) \pmod p = x \pmod p$。
输入格式
输入的第一行包含一个整数 $p$ ($2 \le p \le 10^5$)。
保证 $p$ 是素数。
输出格式
输出一个整数：$\max(f(0), f(1), \dots, f(p - 1))$。
样例
样例输入 1
2
样例输出 1
0
样例输入 2
3
样例输出 2
1
样例输入 3
5
样例输出 3
2
样例输入 4
7
样例输出 4
2
样例输入 5
99991
样例输出 5
20