Sad powers

题意翻译

给你 $q$ 个询问,每次询问 $[l,r]$ 这个区间内满足 $x=a^p(a>0,p>1)$ 的 $x$ 的数量。 数据范围: - $1\leqslant q\leqslant 10^5$。 - $1\leqslant l\leqslant r\leqslant 10^{18}$。 Translated by Eason_AC 2021.10.8

题目描述

You're given $ Q $ queries of the form $ (L,R) $ . For each query you have to find the number of such $ x $ that $ L<=x<=R $ and there exist integer numbers $ a&gt;0 $ , $ p&gt;1 $ such that $ x=a^{p} $ .

输入输出格式

输入格式


The first line contains the number of queries $ Q $ $ (1<=Q<=10^{5}) $ . The next $ Q $ lines contains two integers $ L $ , $ R $ each $ (1<=L<=R<=10^{18}) $ .

输出格式


Output $ Q $ lines — the answers to the queries.

输入输出样例

输入样例 #1

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

输出样例 #1

2
1
0
3
17
1111

说明

In query one the suitable numbers are $ 1 $ and $ 4 $ .