This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them?
设 $p$ 为一个奇素数。计算区间 $[l, r]$ 中二次剩余的个数。
$x$ 是 $p$ 的二次剩余，当且仅当 $x^{(p-1)/2} \equiv 1 \pmod p$。
输入格式
第一行包含 $p, l, r$ ($3 \le p \le 10^{11}, 1 \le l \le r < p$)。保证 $p$ 是一个奇素数。
输出格式
一个整数，即答案。
样例
样例输入 1
11 3 8
样例输出 1
3
样例输入 2
998244353 11451400 919810000
样例输出 2
454174074
样例输入 3
96311898227 25437319919 55129361817
样例输出 3
14846091352