#ifndef LOCAL
#include <bits/stdc++.h>
#define debug(...)
#endif

using namespace std;
// #define int long long
#define cinv(v) for (auto &it:v) cin>>it;
#define coutv(v) for (auto &it:v) cout<< it<<' '; cout<<'\n';
using ll = long long;

const int N = 1e6 + 5;
vector<int> divisors[N];
int dp[N];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    for (int i = 1; i < N; ++i) {
        for (int j = i + i; j < N; j += i) divisors[j].push_back(i);
    }

    for (int i = 2; i < N; ++i) {
        dp[i] = dp[i - 1];
        for (auto &v: divisors[i]) {
            int j = i - v;
            if (gcd(j, i) == v) dp[i]++;
        }
    }
    debug(dp[N-1]);
    int t;
    cin >> t;
    while (t--) {
        int x;
        cin >> x;
        cout << dp[x] << '\n';
    }
}