#include <cstdio>
#include <cstdlib>
using namespace std;
int N,M,T;
int Num[1000];
void init()
{
	scanf("%d\n",&T);
	int a,b;
	int Len;
	for(int i=1;i<=T;i++)
	{
		scanf("%d %d\n",&N,&M);
		Len=0;
		for(int j=0;j<=900;j++) Num[j]=0;
		for(int j=1;j<=N;j++)
		{
			scanf("%d %d\n",&a,&b);
			for(int k=a;k<=b;k++)
			{
				int now=k;
				int pos=0;
				while(now)
				{
					Num[++pos]+=now%M;
					now/=M;
				}
				if(Len<pos) Len=pos;
			} 
		}
		long long Ans=0;
		for(int j=1;j<=Len;j++)
		{
			Num[j]%=M;
			int Res=1;
			for(int k=1;k<=j-1;k++) Res*=M;
			Ans+=Num[j]*Res;
		}
		printf("%lld\n",Ans);
	}
}

int main()
{
	freopen("sumb.in","r",stdin);
	freopen("sumb.out","w",stdout);
	init();
	return 0;
}