#include <cstdio>
#include <memory.h>
using namespace std;

unsigned int m,len,num[40];

void plus(int x,int k)
{
	unsigned int lent=0;
	while (x)
	{
		lent++;
		num[lent]+=x%k;
		x/=k;
	}
	if (lent>len)
		len=lent;
}

unsigned int power(int num,int level)
{
	unsigned int temp=1;
	while (level)
	{
		temp*=num;
		level--;
	}
	return(temp);
}

void printit(void)
{
	unsigned long long i,ans=0;
	for (i=1;i<=len;i++)
		ans+=num[i]*power(m,i-1);
	printf("%d\n",ans);
}

int main(void)
{
	freopen("sumb.in","r",stdin);
	freopen("sumb.out","w",stdout);
	unsigned int i,j,k,t,n,x,y;
	scanf("%d",&t);
	for (i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&m);
		len=0;
		memset(num,0,sizeof(num));
		for (j=1;j<=n;j++)
		{
			scanf("%d%d",&x,&y);
			for (k=x;k<=y;k++)
				plus(k,m);
		}
		for (j=1;j<=len;j++)
			num[j]%=m;
		printit();
	}
	return(0);
}