#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=5000010,MOD=1e9+7;
int T,k,n,m,ans;
bool mark[N];
int prime[N],mu[N],jsq;
int ppow[N];
int qpow(int a,int b)
{
    int mul=1;
    for(;b;b>>=1,a=a*a%MOD) if(b&1) mul=mul*a%MOD;
    return mul;
}
void init()
{
    mark[1]=mu[1]=1;
    for(int i=2;i+10<=N;i++)
    {
        if(!mark[i]) prime[++jsq]=i,mu[i]=-1;
        for(int j=1;j<=jsq;j++)
        {
            if(i*prime[j]+10>N) break;
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=2;i+10<=N;i++) mu[i]=(mu[i]+mu[i-1])%MOD;
    for(int i=1;i+10<=N;i++) ppow[i]=(ppow[i-1]+qpow(i,k))%MOD;
    return;
}
int f(int n,int m)
{
    int res=0;
    for(int l=1,r=0;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        res=(res+(mu[r]-mu[l-1])*(n/l)%MOD*(m/l))%MOD;
    }
    return res;
}
signed main()
{
    freopen("bzoj_4407.in","r",stdin);
    freopen("bzoj_4407.out","w",stdout);
    T=re();k=re();init();
    while(T--)
    {
        n=re();m=re();
        if(n>m) swap(n,m);
        for(int l=1,r=0;l<=n;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            ans=(ans+(ppow[r]-ppow[l-1])*f(n/l,m/l))%MOD;
        }
        printf("%lld\n",(ans+MOD)%MOD);
        ans=0;
    }
    return 0;
}