#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=20005;
int TT,n,t,s;
bool vis[65];
struct node{
	int opt;
	ll x;
}A[N];int cnt;
bool cmp(node a,node b){
	return a.x<b.x;
}
int main(){
	ll x,y,l,r;
	ll a,b;
	scanf("%d",&TT);
	while(TT--){
		scanf("%d",&n);
		scanf("%lld",&x);
		y=x;t=0;s=0;cnt=0;
		while(y){
			vis[t]=y&1;
			if(y&1) s++;
			y>>=1;t++;
		}
		y=(1<<s)-1;
		for(int i=1;i<=n;i++){
			scanf("%lld%lld",&l,&r);
			if(r-l+1>x){
				A[++cnt].opt=1;
				A[cnt].x=0;
				A[++cnt].opt=2;
				A[cnt].x=y+1;
				continue;
			}
			a=b=0;
			for(int i=t;~i;i--){
				if(vis[i]){
					a<<=1;
					if((l>>i)&1) a++;
					b<<=1;
					if((r>>i)&1) b++;
				}
			}
			if(a<=b){
				A[++cnt].opt=1;
				A[cnt].x=a;
				A[++cnt].opt=2;
				A[cnt].x=b+1;
			}else{
				A[++cnt].opt=1;
				A[cnt].x=b;
				A[++cnt].opt=2;
				A[cnt].x=y+1;
				A[++cnt].opt=1;
				A[cnt].x=0;
				A[++cnt].opt=2;
				A[cnt].x=a+1;
			}
		}
		sort(A+1,A+cnt+1,cmp);
		ll ans=0,last=-1;int S=0;
		for(int i=1;i<=cnt;i++){
//			printf("---%d %lld\n",A[i].opt,A[i].x);
			if(S) ans+=A[i].x-last;
			last=A[i].x;
			while(i<cnt and A[i+1].x==A[i].x){
				if(A[i].opt==1) S++;
				else S--;
				i++;
			}
			if(A[i].opt==1) S++;
			else S--;
		}
		printf("%lld\n",ans);
	}
	return 0;
}