Consider some positive integer x. Its prime factorization will be of form x = 2^{k_1} ⋅ 3^{k_2} ⋅ 5^{k_3} ⋅ ...

Let's call x elegant if the greatest common divisor of the sequence k_1, k_2, ... is equal to 1. For example, numbers 5 = 5^1, 12 = 2^2 ⋅ 3, 72 = 2^3 ⋅ 3^2 are elegant and numbers 8 = 2^3 (GCD = 3), 2500 = 2^2 ⋅ 5^4 (GCD = 2) are not.

Count the number of elegant integers from 2 to n.

Each testcase contains several values of n, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer T (1 ≤ T ≤ 10^5) — the number of values of n in the testcase.

Each of the next T lines contains a single integer n_i (2 ≤ n_i ≤ 10^{18}).

Output

Print T lines — the i-th line should contain the number of elegant numbers from 2 to n_i.

Example

Input

4
4
2
72
10


Output

2
1
61
6

Note

Here is the list of non-elegant numbers up to 10:

  * 4 = 2^2, GCD = 2; 
  * 8 = 2^3, GCD = 3; 
  * 9 = 3^2, GCD = 2. 



The rest have GCD = 1.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class F50 {

    static final int MAX_POWER = 59;
    static final long MAX_N = (long)1e18;
    static final int MAX_A = (int)1e6;

    static int mu[] = new int[MAX_POWER + 1];
    static {
        mu[1] = 1;
        mu[2] = -1;
        for(int i = 3; i <= MAX_POWER; ++i) {
            int cur = i;
            mu[i] = 1;
            for(int j = 2; j <= cur; ++j) {
                if(cur % j == 0) {
                    mu[i] *= -1;
                    cur /= j;
                    if(cur % j == 0) {
                        mu[i] = 0;
                        break;
                    }
                }
            }
        }

    }

    static int[] maxBase = new int[MAX_POWER + 1];
    static {
        for(int base = 2; base <= MAX_A; ++base) {
            long cur = base;
            for(int p = 2; p <= MAX_POWER && cur <= MAX_N / base; ++p) {
                cur *= base;
                maxBase[p] = base;
            }
        }
    }

    public static void main(String[] args) {
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = in.nextInt();
        Input[] inputs = new Input[t];
        for(int i = 0; i < t; ++i) {
            inputs[i] = new Input(i, in.nextLong());
        }
        Arrays.sort(inputs, Comparator.comparingLong(a -> a.n));
        for(int i = t - 1; i >= 0; --i) {
            inputs[i].solve();
        }
        Arrays.sort(inputs, Comparator.comparingInt(a -> a.ind));
        for(int i = 0; i < t; ++i) {
            out.println(inputs[i].ans);
        }
        out.flush();
    }

    static class Input{
        int ind;
        long n;
        long ans;
        Input(int ind, long n) {
            this.ind = ind;
            this.n = n;
        }
        void solve() {
            ans = n - 1;
            ans -= getSqrt(n) - 1;
            for(int p = 3; p <= MAX_POWER && binPow(2, p) <= n; ++p) {
                if(maxBase[p] == 0) continue;
                while(binPow(maxBase[p], p) > n) {
                    maxBase[p]--;
                }
                ans += mu[p] * (maxBase[p] - 1);
            }
        }
    }

    static long binPow(long a, long p) {
        long ans = 1;
        while(p > 0) {
            if((p & 1) > 0) {
                ans *= a;
            }
            p >>= 1;
            a *= a;
        }
        return ans;
    }

    static long getSqrt(long x) {
        long a = 1;
        long b = (long)1e9;
        while(a < b) {
            long mid = (a + b) / 2 + 1;
            if(mid * mid <= x) {
                a = mid;
            } else {
                b = mid - 1;
            }
        }
        return a;
    }

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

}