Solution

Let's consider an ordered manner of the pairs i<j where \gcd(i,j)=1 , This helps us to avoid overcounting since unordered pairs overcounts , For some $i$ we want to know what's the count of integers $j$ less than it such that \gcd(i,j)=1 , this is equivalent to $\phi (i)$ Euler Totient Function , since we'll not count a pair $(i,j)$ twice with this way , then we can sum up the values for each integer separately , Formally

However , if you noticed the graph there's already $n$ lines making the graph, Thus

Therefore the expression is

however notice that you're counting \varphi(1)=1 we should exclude it thus the final expression is

By precalculating $\phi (x)$ for all 1 \le x \le 2 \cdot 10^5 , We obtain \mathcal{O}(\sum n) however from the problem statement $\sum n$ isn't bounded , therefore we can speed up the computation by prefix sum.

Now we can answer the test cases in $\mathcal{O}(1)$ time !.

Complexity \mathcal{O}(N\log \log N) where N=2 \cdot 10^5.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int N=200000;
int phi[N+1];
vector<int>sum={0};

void solve(){
    int n;cin>>n;
    cout<<sum[n]-n-1<<"\n";
}

signed main(){
    for(int i=1;i<=N;i++)phi[i]=i;
    for (int i=2;i<=N;i++) {
        if (phi[i]==i) {
            for (int j=i;j<=N;j+=i)
                phi[j]-=phi[j]/i;
        }
    }
    int cur=0LL;
    for(int i=1;i<=N;i++){
        cur+=phi[i];
        sum.push_back(cur);
    }
    int t=1;cin>>t;
    while(t--) solve();
}