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 = ap.

Input

The first line contains the number of queries Q (1 ≤ Q ≤ 105).

The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 1018).

Output

Output Q lines — the answers to the queries.

Example

Input

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


Output

2
1
0
3
17
1111

Note

In query one the suitable numbers are 1 and 4. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class sad_powers {

    static long root(long a) {
        long high = 1000000000;
        long low = 0;
        long ans = 0;
        while (low <= high) {
            long mid = (high + low) / 2;
            if(mid * mid == a){
                return mid;
            }
            if (mid * mid < a) {
                ans = Math.max(ans, mid);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        StringBuilder out = new StringBuilder();
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int c = 0;
        //Set<Long> set = new TreeSet<>();
        long s, n, s1, s2;
        long[] arr = new long[1003332];
        long[] arr2 = new long[1003479];
        for (long i = 2; i <= 1000000; i++) {
            n = i * i;
            while (n <= 1e18 / i) {
                n *= i;
                s = root(n);
                if (s * s != n) {
                    //set.add(n);
                    arr2[c++] = n;
                }
            }
        }
        Arrays.sort(arr2); //faster than set
        arr[0] = arr2[0];
        int p = 1;
        for (int i = 0; i < arr2.length; i++) {
            if(arr[p-1] == arr2[i]) continue;
            arr[p++] = arr2[i];
        }
        /*int p = 0;
        for (Long l : set) {
            arr[p++] = l;
        }*/
        int t = Integer.parseInt(in.readLine());
        String st, temp[];
        for (int k = 0; k < t; k++) {
            st = in.readLine();
            temp = st.split("\\s+");
            long a = Long.parseLong(temp[0]);
            long b = Long.parseLong(temp[1]);
            int l = Arrays.binarySearch(arr, a - 1);
            int r = Arrays.binarySearch(arr, b);
            if (r >= 0) {
                r++;
            }
            if (l >= 0) {
                l++;
            }
            if (l < 0) {
                l = l * -1 - 1;
            }
            if (r < 0) {
                r = r * -1 - 1;
            }
            long ans = r - l;
            s1 = (root(a));
            s2 = (root(b));
            if(s1*s1 == a)
                s1--;
            ans += s2 - s1;
            out.append(ans + "\n");
        }
        System.out.print(out);
    }
}