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*<sup class="upper-index">*p*</sup>.
The first line contains the number of queries *Q* (1 ≤ *Q* ≤ 10<sup class="upper-index">5</sup>).

The next *Q* lines contains two integers *L*, *R* each (1 ≤ *L* ≤ *R* ≤ 10<sup class="upper-index">18</sup>).
In query one the suitable numbers are 1 and 4.
6
1 4
9 9
5 7
12 29
137 591
1 1000000
2
1
0
3
17
1111
20
862 928
758 964
541 789
622 943
328 900
14 764
217 972
461 847
442 468
900 986
518 529
938 993
549 851
690 944
484 601
320 910
98 868
816 915
765 880
551 770
1
4
5
6
14
32
20
9
0
2
1
1
6
4
4
15
26
2
2
4
#include <bits/stdc++.h>

using namespace std;

// for calculations function
#define MIN_BASE 2
#define MAX_BASE 1e6
#define MAX_VALUE 1e18

// for square_root function
#define SQRT_UPPER 1e9 + 1

// for debugging
#define QUANTITY 20
#define DEBUG false

set <long long> powers;

long long long_sqrt (long long number)
{
    long long upper = SQRT_UPPER;
    long long lower = 0;
    while (lower < upper - 1)
    {
        long long middle = (upper + lower) / 2;
        long long power_2 = middle * middle;
        if (power_2 > number)
        {
            upper = middle;
        }
        else
        {
            lower = middle;
        }
    }
    return lower;
}

void calculate_all_powers ()
{
    for (long long i = MIN_BASE; i <= MAX_BASE; i++)
    {
        for (long long cur_power = i * i * i;
                cur_power <= MAX_VALUE; cur_power *= i)
        {
            long long square_root = long_sqrt (cur_power);
            if (square_root * square_root != cur_power)
                powers.insert (cur_power);
            if (cur_power > MAX_VALUE / i) break;
        }
    }

}

void print_set (int quantity_to_print)
{
    for (set<long long>::iterator it = powers.begin();
            quantity_to_print-- > 0 && it != powers.end(); ++it)
        cout << *it<< " ";
}

int get_length (set<long long>::iterator itlow, set<long long>::iterator ithigh)
{
    if (itlow == ithigh) return 0;
    printf("%lld %lld \n", *itlow ,*ithigh);
    return distance(ithigh, itlow);
}

void answer_queries (int queries_size)
{
    while (queries_size-- > 0)
    {
        long long left, right; cin >> left >> right;

        long long answer =  get_length(powers.upper_bound(right), powers.lower_bound(left));
        answer += long_sqrt(right) - long_sqrt(left - 1);
        printf("%lld\n", answer);
    }
}

int main() {
    calculate_all_powers ();
    if (DEBUG) print_set (QUANTITY);
    int queries_size; cin >> queries_size;
    answer_queries (queries_size);
    return 0;
}
