Start: 2025-08-22 11:00:00

暑期训练赛S01

End: 2025-09-06 11:00:00
Now  2025-09-13 19:08:42  类型: IOI  状态: Ended 

P3. 互质序列(rlprime)
Description

给出两个数 A, BB \geq A),问有多少个序列满足以下条件:

1. 序列是递增的。

2. 所有数字属于区间 [A, B](包括 A 和 B,B - A \leq 100)。

3. 序列中的所有数字两两互质。


Input

一行输入两个数 A、B。其中 1 \leq A \leq B \leq 1e18B - A \leq 100

Output

输出对应的答案。

Examples

Input

2 4

Output

5
Hint

- 对于 25% 的数据:1 \leq A \leq B \leq 10^7B - A \leq 30

- 对于 40% 的数据:1 \leq A \leq B \leq 10^{12}B - A \leq 50

- 对于 100% 的数据:1 \leq A \leq B \leq 10^{18}B - A \leq 100

样例解释:

满足条件的序列为:(2)、(3)、(4)、(2,3)、(3,4)。

Submit

题目参数
Time Limit 1 second
Memory Limit 256 MB
Submit