How many pair gcd greater than 1

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

ll phi[maxx];
ll mark[maxx];
ll cu_phi[maxx];


void phi_sum(){
    cu_phi[1]=1;
    cu_phi[2]=1;
    for(int i=2;i<=maxx;i++) {cu_phi[i]=phi[i]+cu_phi[i-1];}
}

void sieve_phi(){
    for(int i=1;i<=maxx;i++) phi[i]=i;
    phi[1]=1;
    mark[1]=1;
    for(int i=2;i<=maxx;i++){
        if(!mark[i]){
            for(int j=i;j<=maxx;j+=i){
                mark[j]=1;
                phi[j]=phi[j] / i*(i-1);
            }
        }
    }
}

int main()
{
    sieve_phi();
    phi_sum();
    int t,cas=0;
    cin>>t;
    while(t--){
        ll x;
        cin>>x;
        cout<<"Case "<<++cas<<": "<<((x*(x+1))/2)-cu_phi[x]<<endl;
    }
}