#include <bits/stdc++.h>

using namespace std;

vector<int> snt(int n) {
    vector<bool> f(n + 1, true);
    f[0] = f[1] = false;
    for (int p = 2; p * p <= n; ++p) {
        if (f[p]) {
            for (int i = p * p; i <= n; i += p) {
                f[i] = false;
            }
        }
    }
    vector<int> c;
    for (int p = 2; p <= n; ++p) {
        if (f[p]) {
            c.push_back(p);
        }
    }
    return c;
}

int cnt(int a, const vector<int>& p) {
    int count = 0;
    for (int y : p) {
        int y2 = y * y;
        if (y2 > a) break;
        for (int z : p) {
            int z3 = z * z * z;
            if (y2 + z3 > a) break;
            int x = a - y2 - z3;
            if (x >= 2 && find(p.begin(), p.end(), x) != p.end()) {
                ++count;
            }
        }
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int ln = *max_element(a.begin(), a.end());
    vector<int> p = snt(ln);

    for (int c : a) {
        int result = cnt(c, p);
        cout << result << " ";
    }

    return 0;
}