Gats and the Leftover Treaty

Time limit: 2000 msMemory limit: 256 MB

Gats supervises $N$ cats after a day of fishing. Cat $i$ caught $A_i$ fish.

For a chosen positive integer bowl capacity $X$ , each cat places their fish into as many full bowls of exactly $X$ fish as possible. Cat $i$ then has a leftover amount $r_i$ , defined as the unique integer satisfying

0 \le r_i < X

and

A_i \equiv r_i \pmod X.

A capacity $X$ is called harmonious when both of the following conditions hold:

All cats have the same leftover amount: $r_1=r_2=\cdots=r_N$ .

Given an allowed interval $[L,R]$ , determine how many integer capacities in this interval are harmonious.

Input

The first line contains three integers $N$ , $L$ , and $R$ ( $1 \le N \le 2 \times 10^5$ , ), representing the number of cats and the allowed range of bowl capacities.

Output

Print one integer: the number of harmonious bowl capacities $X$ satisfying $L \le X \le R$ .

Samples

Sample 1

Input

3 2 20
11 23 35

Output

The harmonious capacities are $2$ , $3$ , $4$ , $6$ , and $12$ . For each of them, all three cats have the same leftover, and that leftover is relatively prime to the capacity.

Sample 2

Input

2 2 10
12 12

Output

Because both cats caught the same number of fish, their leftovers are equal for every capacity. Within the allowed range, only capacities and also satisfy the coprimality requirement.

Gats and the Leftover Treaty

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions

Sample 3