#include <bits/stdc++.h>
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define OFF(x, i) ((x) & ~(1LL << (i)))
#define ON(x, i) ((1LL << (i)) | (x))
#define CNT(x) __builtin_popcountll(x)
#define task""
#define freopen freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout);
#define endl '\n'
#define F first
#define S second
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)

using namespace std;
int t, n;
int const N = 2e6 + 6;
int p[N], pre[N];

void Sieve()
{
    memset(p, 0, sizeof p);
    p[1] = 1;
    for (int i = 2; i * i <= N; i++)
    {
        if (p[i] == 0)
            for (int j = i * i; j <= N; j += i)
                p[j] = 1;
    }
}

void Prefix()
{
    pre[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        if (!p[i]) pre[i] = pre[i - 1] + 1;
        else pre[i] = pre[i - 1];
    }
}

void Sub1()
{
    int cnt = 0, t1 = 0, t2 = 0, sum = 0;
        for (int i = 1; i <= n - 2; i++)
        {
            for (int j = i + 1; j <= n - 1; j++)
                for (int k = j + 1; k <= n; k++)
            {
                if ((!p[i + j] && !p[j + k] && !p[i + k]) || (p[i + j] && p[i + k] && p[j + k])) cnt++;
            }
        }
        cout << cnt << endl;
}

void Sub2()
{
    vector <int> x(n + 1, 0), y(n + 1, 0);
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
    {
        if (p[i + j]) x[i]++, x[j]++;
        else y[i]++, y[j]++;
    }

    long long diff = 0;
    for (int i = 1; i <= n; i++) diff += 1LL * x[i] * y[i];
    diff /= 2;
    long long total = 1LL * n * (n - 1) * (n - 2)/6;
    cout << total - diff << endl;
}

void Sub3()
{
    long long diff = 0;
    for (int i = 1; i < n; i++)
    {
        int x = pre[i + n] - pre[i];
        int y = n - x - 1;
        diff += 1LL * x * y;
    }
    diff /= 2;
    long long total = 1LL * n * (n - 1) * (n - 2)/6;
    cout << total - diff << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen

    Sieve();
    Prefix();
    cin >> t;
    while (t--)
    {
        cin >> n;
        Sub2();
    }

    cerr << endl << TIME << endl;
    return 0;
}