Co-Prime Enemy Pair

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 9223372036854775806
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define PI 2*acos(0.0)
ll mod(ll B,ll M){ll X=B%M; if(X>=0) return X; else return M+X;}
///cin.ignore();
ll max(ll a,ll b) {if(a>b) return a; else return b;} ll min(ll a,ll b) {if(a<b) return a; else return b;}
ll fx4[]={1,-1,0,0}; ll fy4[]={0,0,1,-1};
const ll maxx=10000000;
int status[(maxx>>5)+2];

bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}
int Set(int N, int pos)
{
    return N=(N|(1<<pos));
}
vector<ll>Primes;
void sieve()
{
    ll i,j,sqrtN;
    sqrtN=ll(sqrt(maxx))+1;
    Primes.pb(2);
    for(int i=3;i<=maxx;i+=2)
    {
        if(check(status[i>>5],i&31)==0)
        {
            Primes.pb(i);

            if(i<=sqrtN)
            for(j=i*i;j<=maxx;j+=(i<<1))
            {
                status[j>>5]=Set(status[j>>5],j & 31);
            }
        }
    }
}
ll one[1000006],cnt[1000006];
ll lim=1000000;
ll A[1000006],cA[1000006];
void phi()
{
    A[0]=0;
    for(ll i=1;i<=lim;i++) A[i]=i;
    for(ll x:Primes){
        for(ll i=x;i<=lim;i+=x){
            A[i]=(A[i]*(x-1))/x;
        }
    }
}
int main()
{
    //freopen("C:/Users/Md Faizul Haque/Desktop/Solving/input.txt","r",stdin);
    //freopen("C:/Users/Md Faizul Haque/Desktop/Solving/output.txt","w",stdout);
    sieve();
    phi();
    ll t,n,m,x,y,w,k,q,r,p,cs;
    for(auto x:Primes){
        y=x;
        while(y<=lim){
            one[y]=1;
            y=y*x;
        }
    }
    for(int i=1;i<=lim;i++){
        cnt[i]=cnt[i-1]+one[i];
    }
    for(int i=1;i<=lim;i++){
        if(one[i]==0){
            cA[i]=cA[i-1];
        }
        else{
            cA[i]=cA[i-1]+A[i];
        }
    }

    cin>>t;
    for(cs=1;cs<=t;cs++){
        cin>>n;
        ll ans=cA[n]-cnt[n];
        printf("Case %lld: %lld\n",cs,ans);
    }

    return 0;
}