Sequence Sum 2

Time limit2sMemory limit1024 MB

Summary

Given S and T up to 1e14, compute the sum of a_i for i from S to T, where a_i counts even divisors of i minus odd divisors.

Level: Medium6 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

For a positive integer $n$ , let $d_1, d_2, \cdots, d_k$ be all of its positive divisors. Define $a_n = (-1)^{d_1} + (-1)^{d_2} + \cdots + (-1)^{d_k}$ .

Given positive integers $S$ and $T$ , find $\sum_{i=S}^{T} a_i$ .

Input

The first line contains positive integers $S$ and $T$ , separated by a space. $(1 \le S \le T \le 10^{14})$

Output

Print $\sum_{i=S}^{T} a_i$ .

Examples3

Example 1
Input
```
1 5
```
Expected output
```
-4
```
Example 2
Input
```
8 8
```
Expected output
```
2
```
Example 3
Input
```
16 17
```
Expected output
```
1
```