您将获得 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。