#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

const ll Mod=;

ll f[],sum[],p[],s[];

bool mark[];

ll K,n,m;

ll read(){

    ll t=,f=;char ch=getchar();

    while (ch<''||''<ch){if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

    return t*f;

}

ll Pow(ll x,ll y){

    ll res=;

    while (y){

        if (y%) res=(res*x)%Mod;

        y/=;

        x=(x*x)%Mod;

    }

    return res;

}

void init(){

    f[]=;

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

        if (!mark[i]){

            p[++p[]]=i;

            s[p[]]=Pow(i,K);

            f[i]=s[p[]]-;

        }

        for (int j=;j<=p[]&&p[j]*i<=;j++){

            mark[p[j]*i]=;

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

                f[i*p[j]]=f[i]*s[j]%Mod;

                break;

            }

            f[i*p[j]]=f[i]*f[p[j]]%Mod;

        }

    }

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

     sum[i]=sum[i-]+f[i]%Mod;

}

int main(){

    int T=read();K=read();

    init();

    while (T--){

        n=read();m=read();

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

        int j=;

        ll ans=;

        for (int i=;i<=n;i=j+){

            j=std::min(n/(n/i),m/(m/i));

            ans+=(((n/i)*(m/i)%Mod)*(sum[j]-sum[i-]))%Mod;

            ans%=Mod;

        }

        printf("%lld\n",ans);

    }

    return ;

}