UVA 12425 - Best Friend

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<ll> prime;
char vis[1000100];
#define sz 1000000
void sieve()
{
    prime.push_back(2);
    ll sqrtn = sqrt(sz),i,j;
    for(i=3; i<=sqrtn; i+=2)
    {
        if(vis[i]==0)
        {
            for(j=i*i; j<=sz; j+=2*i)
                vis[j]=1;
        }
    }
    for(i=3; i<=sz; i+=2)
        if(vis[i]==0)
            prime.push_back(i);
}
vector<ll>vec,vec1,phi;
ll calc(ll nm)
{
    ll res=nm,i;
    ll sqrtn=sqrt(nm);
    for(i=0; i<prime.size()&&prime[i]<=sqrtn; i++)
    {
        if(nm%prime[i]==0)
        {
            while((nm%prime[i])==0)
            {
                nm/=prime[i];
            }
            res/=prime[i];
            res*=prime[i]-1;
        }
    }
    if(nm!=1)
    {
        res/=nm;
        res*=nm-1;
    }
    return res;
}
main()
{
    timesave;
    sieve();
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        ll n,q,i,sq;
        cin>>n>>q;
        vec.clear();
        vec1.clear();
        phi.clear();
        sq=sqrt(n);

        for(i=1; i<=sq; i++)
        {
            if(n%i==0)
            {
                vec.push_back(i);
                if(n/i!=i)
                {
                    vec.push_back(n/i);
                }
            }
        }
        sort(vec.begin(),vec.end());
        vec1.clear();
        for(i=0; i<vec.size(); i++)
        {
            phi.push_back(calc(n/vec[i]));
            if(i)
            {
                phi[i]+= phi[i-1];/// for comulative sum
            }
        }
        ll nm;
        printf("Case %ld\n",cs++);
        for(i=1; i<=q; i++)
        {
            cin>>nm;
            if(nm>=n)
            {
                printf ( "%lld\n", n );/// sob guloi answer
                continue;
            }
            if(nm<1)
            {
                printf ( "%lld\n", 0 );///kono tai ans hobe na
                continue;
            }
            ll pos =upper_bound(vec.begin(),vec.end(),nm )-vec.begin();
            pos--;
            printf ( "%lld\n", phi[pos] );
        }
    }
}