CF955C.Sad powers

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>0 , p>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.

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