#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX = 2000005;
bool isPrime[MAX];

void sieve() {
    fill(isPrime, isPrime + MAX, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAX; j += i) isPrime[j] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    sieve();

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        // deg[i] là số lượng đỉnh kề với i bằng dây xanh (prime sum)
        vector<int> deg(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (isPrime[i + j]) {
                    deg[i]++;
                    deg[j]++;
                }
            }
        }

        ll total_triangles = (ll)n * (n - 1) * (n - 2) / 6;
        ll mixed_triangles = 0;

        // Tính số tam giác lai (mixed) dựa trên độ xanh
        for (int i = 1; i <= n; i++) {
            // Với mỗi đỉnh i, số tam giác lai có 1 đỉnh là i và 2 đỉnh kề xanh là C(deg[i], 2)
            // Chia 2 vì mỗi tam giác lai có đúng 2 đỉnh kề xanh (và 1 đỉnh kề vàng)
            mixed_triangles += (ll)deg[i] * (deg[i] - 1) / 2;
        }

        // Số tam giác toàn xanh = tổng tam giác - tam giác lai
        cout << total_triangles - mixed_triangles << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX = 2000005;
bool isPrime[MAX];
int cnt[MAX]; // cnt[s] là số cách viết s = i + j (i < j) trong [1, n]

void sieve() {
    fill(isPrime, isPrime + MAX, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAX; j += i) isPrime[j] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        // 1. Tính tổng số cạnh xanh trong đồ thị
        // S = sum(deg[i]) / 2
        // Thay vào đó, ta dùng mảng cnt để đếm tần số tổng.

        // 2. Tính tổng các tích deg[i] * (n - 1 - deg[i])
        // sum(deg[i] * (n - 1 - deg[i])) = (n - 1) * sum(deg[i]) - sum(deg[i]^2)

        // sum(deg[i]) = 2 * S
        // sum(deg[i]^2) = sum(sum_{j} (indicator(i,j) + indicator(j,i))^2) / 2? Không.
        // sum(deg[i]^2) = sum_{i} (sum_{j} indicator(i,j))^2
        //               = sum_{i} sum_{j} sum_{k} indicator(i,j) indicator(i,k)
        //               = sum_{j, k} degree(common neighbors of j and k)
        //               = sum_{j, k} (nghệp của j và k)

        // Tuy nhiên, có một cách đếm trực tiếp hơn:
        // Xét 2 đỉnh j, k. 
        // Nếu (j, k) là xanh, thì có bao nhiêu đỉnh i tạo thành tam giác xanh với j, k?
        // Nếu (j, k) là vàng, thì có bao nhiêu đỉnh i tạo thành tam giác xanh với j, k (tức là i-j xanh và i-k xanh)?

        // Cach 2 trong solutions: 
        // d = sum_{i=1 to n} ( (so chan xanh tu i+) * (so chan vang tu i+) )
        // Su dung precomputed array cnt.

        // Reset cnt for range [2, 2n]
        // Tính cnt[s]: số cặp (i, j) i < j, i+j = s, 1 <= i, j <= n.
        // i + j = s => i >= max(1, s - n) va i <= min(n, s - 1)
        // i < j => i < s - i => 2i < s => i < s/2.

        // De toi uu hoa, ta co the tinh truc tiep.
        // Suy dinh lai bai toan:
        // Ket qua = Tong so tam giac - (sum(deg[i] * (n - 1 - deg[i])) / 2)
        // Can tinh: S1 = sum(deg[i]) va S2 = sum(deg[i]^2)

        // S1 = sum_{s la so nguyen to} cnt[s]
        // S2 = sum_{s} cnt[s] * (cnt[s] - 1) + sum_{s} cnt[s] * (so cap (i, j) i+j=s ma co 1 diem chung)
        // Cach nay phuc tap.

        // Tot hon, ta chi can tinh S1 va S2.
        // S1 = sum_{s} cnt[s]
        // S2 = sum_{i} deg[i]^2
        // S2 = sum_{i} (sum_{j} indicator(i, j))^2 = sum_{i} sum_{j} sum_{k} indicator(i, j) indicator(i, k)
        //     = sum_{j, k} (so diem i chung cua j va k)
        //     = sum_{j, k} (deg[j] + deg[k] - ...)? Không.
        //     = sum_{x} (deg[x]) * (deg[x])? Không.

        // S2 = sum_{s1} sum_{s2} (so cap (i, j) sao cho i+j = s1 và i+k = s2)? 
        // De don gian, ta chi can tinh S2 bang cach thuc hien vong lap.
        // Nhung kich thuoc n len toi 10^6, n^2 khong duoc.

        // Cach 2 trong solutions su dung vong lap O(n) tinh xong toan bo.
        // Cach do:
        // d = 0;
        // for(i = 1; i <= n; ++i) {
        //     x = s[n + i] - s[i] - (i == 1); // x = so luong so nguyen to trong (i, n+i] - so luong so nguyen to trong [1, i]
        //                                      // That ra x la so luong so nguyen to p sao cho i < p <= n + i.
        //     // De co the tao canh xanh (i, j), can i < j <= n va i + j la nguyen to.
        //     // i + j la nguyen to p => j = p - i.
        //     // Dieu kien: i < p - i <= n => 2i < p <= n + i.
        //     // Do do x chinh la deg[i] (so luong j).
        //     d += x * (n - 1 - x);
        // }
        // cout << n*(n-1)*(n-2)/6 - d/2 << endl;

        // Day la phien ban O(N) sau khi co Sieve.
        // Chac chan la toi uu nhat.

        // Thuc hien:
        vector<int> pref(2 * MAX, 0); // Phan bao tu Sieve
        for(int i = 1; i < 2 * MAX; i++) {
            pref[i] = pref[i-1] + isPrime[i];
        }

        // Tinh S1 va S2 bang cach truc tiep theo cong thuc tren
        // De tiet kiem bien, ta chi can tinh d truc tiep.

        ll d = 0;
        for (int i = 1; i <= n; i++) {
            // x = deg[i]
            // Can tim so p: i < p - i <= n, p la nguyen to
            // 2i < p <= n + i
            int x = pref[n + i] - pref[2 * i]; 
            // Kiem tra: p > 2i. p <= n + i.
            // Neu i > 1, p >= 2i + 1.
            // Neu i = 1, p > 2. 
            // Cong thuc tren chinh xac.

            d += (ll)x * (n - 1 - x);
        }

        cout << (ll)n * (n - 1) * (n - 2) / 6 - d / 2 << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX = 2000005;
bool isPrime[MAX];
int pref[MAX];

void sieve() {
    fill(isPrime, isPrime + MAX, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAX; j += i) isPrime[j] = false;
        }
    }
    // Tính mảng tiền tố
    for (int i = 1; i < MAX; i++) {
        pref[i] = pref[i-1] + isPrime[i];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        // Tính S1 = sum(deg[i]) và S2 = sum(deg[i]^2) trực tiếp
        ll S1 = 0;
        ll S2 = 0;

        for (int i = 1; i <= n; i++) {
            // deg[i] = count of primes p such that 2i < p <= n + i
            int deg = pref[n + i] - pref[2 * i];
            S1 += deg;
            S2 += (ll)deg * deg;
        }

        // D = sum(deg[i] * (n - 1 - deg[i])) = (n - 1) * S1 - S2
        ll D = (ll)(n - 1) * S1 - S2;

        ll total = (ll)n * (n - 1) * (n - 2) / 6;

        cout << total - D / 2 << '\n';
    }
    return 0;
}