Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rLL rgt LL
#define inf 0x7f7f7f7f
#define p 1000000007
#define N 5000000
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
int n,m,T,t,k,mu[N+3],f[N+3],pr[N],res,ans;
bool v[N+3];
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline int Pow(rLL a) {
    rint b=k;rLL res=1;
    for(;b;b>>=1,a=a*a%p)
    if(b&1) res=res*a%p;return res;
}
inline void init() {
    rint i,j,c;mu[1]=1;
    for(i=2;i<=N;i++) {
        if(!v[i]) pr[++t]=i,mu[i]=-1;
        for(j=1;j<=t;++j) {
            c=i*pr[j];if(c>N) break;v[c]=1;
            if(i%pr[j]) mu[c]=-mu[i];
            else break;
        }
    }
    for(i=1;i<=N;i++) {
        c=Pow(i);
        for(j=i;j<=N;j+=i)
            f[j]=(f[j]+c*mu[j/i])%p;
    }
    for(i=2;i<=N;i++) f[i]=(f[i]+f[i-1])%p;
}
inline void solve() {
    if(n>m) n^=m^=n^=m;ans=0;
    for(rint l=1,r;l<=n;l=r+1) {
        r=min(n/(n/l),m/(m/l)),
        ans=(ans+1ll*(n/l)*(m/l)%p*(f[r]-f[l-1])%p)%p;
    }printf("%d\n",(ans+p)%p);
}
int main()
{
    T=read(),k=read(),init();
    while(T--) n=read(),m=read(),solve();
    return 0;
}

devil.