#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long int big_mode(long long int base,long long int po)
{
    if(po==0)
        return 1;
    else if(po%2==0)
    {
        long long int temp=big_mode(base,po/2);
        return ((temp%MOD)*(temp%MOD))%MOD;
    }
    else
    {
        return ((base%MOD)*big_mode(base,po-1))%MOD;
    }
}
int main()
{
    long long int t,tc=0,po,base,p,sum;
    scanf("%lld",&t);
    while(tc<t)
    {
        sum=0;
        scanf("%lld%lld",&base,&po);

        p=big_mode(base,po);
        //p=pow(base,po);
       // cout<<p<<endl;
        for(long long int i=1;i<=sqrt(p);i++)
        {
            if(i==sqrt(p))
                sum+=i;
            else if(p%i==0)
            {
                sum+=i;
                sum+=p/i;
               // cout<<i<<" "<<p/i<<endl;
            }
        }
        printf("Case %lld: %lld\n",++tc,sum%MOD);
    }
    return 0;
}