#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL P=1e9+7;
LL f[65][2][2][2][2];
LL a[65],b[65],k;
LL dfs(int x,bool f1,bool f2,bool f3,bool f4)
{
	if(x==0)return f1;
	if(f[x][f1][f2][f3][f4]+1)return f[x][f1][f2][f3][f4];
	int up1=f2?k-1:a[x],up2=f3?k-1:b[x];LL ans=0;
	for(int i=0;i<=up1;i++)for(int j=0;j<=up2;j++)
	{
		if(!f4&&j>i)break;	
		ans+=dfs(x-1,f1||j>i,f2||i!=up1,f3||j!=up2,f4||j!=i);
		ans%=P;
	}
	f[x][f1][f2][f3][f4]=ans;
	return ans;
} 
LL calc(LL n,LL m)
{
	if(m>n)m=n;
	int len1=0,len2=0;
	while(n)a[++len1]=n%k,n/=k;
	while(m)b[++len2]=m%k,m/=k;
	for(int i=len2+1;i<=len1;i++)b[i]=0;
	memset(f,-1,sizeof(f));
	return dfs(len1,0,0,0,0);
}
int main()
{
	int t;scanf("%d%lld",&t,&k);
	while(t--)
	{
		LL n,m;scanf("%lld%lld",&n,&m);
		printf("%lld\n",calc(n,m));
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL P=1e9+7;
LL f[65][2][2][2][2];
LL a[65],b[65],k;
LL dfs(int x,bool f1,bool f2,bool f3,bool f4)
{
	if(x==0)return f1;
	if(f[x][f1][f2][f3][f4]+1)return f[x][f1][f2][f3][f4];
	int up1=f2?k-1:a[x],up2=f3?k-1:b[x];LL ans=0;
	for(int i=0;i<=up1;i++)for(int j=0;j<=up2;j++)
	{
		if(!f4&&j>i)break;	
		ans+=dfs(x-1,f1||j>i,f2||i!=up1,f3||j!=up2,f4||j!=i);
		ans%=P;
	}
	f[x][f1][f2][f3][f4]=ans;
	return ans;
} 
LL calc(LL n,LL m)
{
	if(m>n)m=n;
	int len1=0,len2=0;
	while(n)a[++len1]=n%k,n/=k;
	while(m)b[++len2]=m%k,m/=k;
	for(int i=len2+1;i<=len1;i++)b[i]=0;
	memset(f,-1,sizeof(f));
	return dfs(len1,0,0,0,0);
}
int main()
{
	int t;scanf("%d%lld",&t,&k);
	while(t--)
	{
		LL n,m;scanf("%lld%lld",&n,&m);
		printf("%lld\n",calc(n,m));
	}
	return 0;
}