9737: ABC195 —— F - Coprime Present
[Creator : ]
Description
You have $B-A+1$ cards: for each integer from $A$ through $B$, you have one card with that integer written on it. You will give some of them (possibly none) to your pet, Snuke.
Snuke will be happy if, for every pair of different cards, the numbers written on them are pairwise coprime; otherwise, he will be sad.
How many sets of cards will make Snuke happy?
Snuke will be happy if, for every pair of different cards, the numbers written on them are pairwise coprime; otherwise, he will be sad.
How many sets of cards will make Snuke happy?
Input
Input is given from Standard Input in the following format:
```
$A$ $B$
```
```
$A$ $B$
```
Output
Print the number of sets of cards that will make Snuke happy. The constraints guarantee that the answer is less than $2^{63}$.
Constraints
- $1 \leq A \leq B \leq 10^{18}$
- $B-A \leq 72$
- All values in input are integers.
- $B-A \leq 72$
- All values in input are integers.
Sample 1 Input
2 4
Sample 1 Output
6
You have three cards with 2, 3, and 4 written on them. The following six sets of cards will make Snuke happy:
- {}
- {2}
- {3}
- {4}
- {2,3}
- {3,4}
Sample 2 Input
1 1
Sample 2 Output
2
The following two sets of cards will make Snuke happy:
- {}
- {1}
Sample 3 Input
123456789000 123456789050
Sample 3 Output
2125824