← 返回题目列表

Codeforces · 955/C

C. 悲伤的力量

中文机器翻译题面 查看原题

您将获得 Q 个 (L, R) 形式的查询。

对于每个查询,您必须找到满足 L ≤ x ≤ R 的 x 的数量,并且存在整数 a > 0、p > 1 使得 x = ap。

输入

第一行包含查询数量 Q (1 ≤ Q ≤ 105)。

接下来的 Q 行包含两个整数 L、R (1 ≤ L ≤ R ≤ 1018)。

输出

输出 Q 行 — 查询的答案。

示例

输入 #1

6
1 4
9 9
5 7
12 29
137 591
1 1000000

输出 #1

2
1
0
3
17
1111

注意

在查询一中,合适的数字是 1 和 4。