#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000007

#define maxn 5000005

ll n,m,K;

ll Pow(ll a,ll b){

    ll res=;

    while(b){

        if(b%)res=res*a%mod;

        b>>=;a=a*a%mod;

    }

    return res;

}

bool vis[maxn];

ll prime[maxn],G[maxn],sum[maxn],mu[maxn],mm;

void init(){

    mu[]=G[]=;

    for(int i=;i<maxn;i++){

        if(!vis[i]){

            prime[++mm]=i;

            mu[i]=-;

            G[i]=Pow(i,K)-;

            if(G[i]<)G[i]+=mod;

        }

        for(int j=;j<=mm;j++){

            if(i*prime[j]>=maxn)break;

            vis[i*prime[j]]=;

            if(i%prime[j]==){

                mu[i*prime[j]]=;

                G[i*prime[j]]=G[i]*Pow(prime[j],K)%mod;

                break;

            }

            else {

                mu[i*prime[j]]=-mu[i];

                G[i*prime[j]]=G[i]*G[prime[j]]%mod;

            }

        }

    }

    for(int i=;i<maxn;i++)

        sum[i]=(sum[i-]+G[i])%mod;

}

int main(){

    int t;cin>>t>>K;

    init();

    while(t--){

        cin>>n>>m;

        if(n>m)swap(n,m);

        ll ans=;

        for(int l=,r;l<=n;l=r+){

            r=min(n/(n/l),m/(m/l));

            ll tmp=((sum[r]-sum[l-])%mod+mod)%mod;

            ans=(ans+tmp*(n/l)%mod*(m/l)%mod)%mod;

        }

        cout<<ans<<'\n';

    }

}