#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <iomanip>
using namespace std;
int a,b,c,d,e,r[100],l,m,n,k,s[100],t=0,z;
long long ac;
void zhuanhuan(int x,int y)
{
	while (x!=0)
	{
		r[k]=x%y;
		k++;
		x/=y;
	}
}
void zh(void)
{
	ac=0;
	int i;
	for (i=0;i<t;i++) 
		ac+=s[i]*(int)pow((double)d,(double)i);
}
int main(void)
{
	freopen ("sumb.in","r",stdin);
	freopen ("sumb.out","w",stdout);
	scanf("%d",&a);
	for (b=0;b<a;b++)
	{
		scanf("%d%d",&c,&d);
		for (e=0;e<t;e++) s[e]=0;
		t=0;
		for (e=0;e<c;e++)
		{
			scanf("%d%d",&l,&m);
			for (n=l;n<=m;n++)
			{
				for (z=0;z<k;z++) r[z]=0;
				k=0;
				zhuanhuan(n,d);
				if (k>t) t=k;
				for (z=0;z<t;z++) s[z]=(s[z]+r[z])%d;
			}
		}
		zh();
		printf("%lld\n",ac);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}