LO 1007 TLE

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define Faster  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll coprime(ll a)
{
    ll ans=a,i;
    for(i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            while(a%i==0)
            {
                a=a/i;
            }
            ans=ans-(ans/i);
        }
    }
    if(a>1) ans=ans-(ans/a);

    return ans;
}

int main()
{
   Faster
   ll t,a,c,d,e=0,f,i,j,k,l;
   cin>>t;
   for(f=1;f<=t;f++)
   {
       e=0;
       cin>>a>>c;
       for(i=a;i<=c;i++)
       {
           d=coprime(i);
           e+=(d*d);
       }
       printf("Case %lld: %lld\n",f,e);
   }
   return 0;
}