E. Elliptic Curve Problem
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them?

Let $$$p$$$ be an odd prime. Compute the number of quadratic residues in $$$[l, r]$$$.

$$$x$$$ is a quadratic residue of $$$p$$$ iff $$$x^{(p-1)/2} \equiv 1 \pmod p$$$.

Input

In the first line, $$$p, l, r$$$ ($$$3\leq p \leq 10^{11}, 1\leq l\leq r \lt p$$$). It's guaranteed that $$$p$$$ is an odd prime.

Output

One integer — the answer.

Examples
Input
11 3 8
Output
3
Input
998244353 11451400 919810000
Output
454174074
Input
96311898227 25437319919 55129361817
Output
14846091352