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*}$.

Input

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

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

Note

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