#include <bits/stdc++.h>

using namespace std;

inline long long pow2(long long a){return a*a;}
inline long long pow3(long long a){return a*a*a;}
inline long long pow4(long long a){return a*a*a*a;}

int main() {
    long t;
    cin >> t;
    long mx = -1;
    long a[t];
    for(long i = 0; i < t; i++){
        cin >> a[i];
        if(a[i] > mx) mx = a[i];
    }

    int b[mx+1];
    for(long i = 0; i < mx+1; i++) b[i] = 0;

    int pr = pow(100000000, 0.5)+1;

    vector<long> primes;
    primes.push_back(2);
    for(int k = 3; k <= pr; k++){
        bool isPrime = true;
        for(auto p : primes){
            if(k % p == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) primes.push_back(k);
    }

    int x = primes.size();

    long long sum = 0;
    for(int i = 0; i < x; i++){
        sum = 0;
        sum += pow4(primes[i]);
        if(sum > mx){
            sum -= pow4(primes[i]);
            break;
        }
        for(int j = 0; j < x; j++){
            sum += pow3(primes[j]);
            if(sum > mx){
                sum -= pow3(primes[j]);
                break;
            }
            for(int k = 0; k < x; k++){
                sum += pow2(primes[k]);
                //cout << sum << endl;
                if(sum > mx){
                    sum -= pow2(primes[k]);
                    break;
                }
                b[sum] = 1;
                sum -= pow2(primes[k]);
            }
            sum -= pow3(primes[j]);
        }
        sum -= pow4(primes[i]);
    }

    for(long tt = 0; tt < t; tt++){
        long long res = 0;
        for(long i = 0; i < a[tt]+1; i++) res += b[i];
        cout << res << endl;
    }

    return 0;
}