#include<cstdio>
using namespace std;
typedef long long ll;
const int N=3000005;
int TT,n,t,s,rt;
bool vis[65];
struct node{
	int l,r;
	ll sum,flag;
}T[N];int cnt;
void change(int &p,ll x,ll y,ll l,ll r){
	if(!p){
		p=++cnt;
		T[p].l=T[p].r=0;
		T[p].sum=T[p].flag=0;
	}
	if(T[p].flag) return;
	if(l<=x and y<=r){
		T[p].flag=1;
		T[p].sum=y-x+1;
		return;
	}
	ll mid=(x+y)>>1;
	if(l<=mid) change(T[p].l,x,mid,l,r);
	if(mid<r) change(T[p].r,mid+1,y,l,r);
	T[p].sum=T[T[p].l].sum+T[T[p].r].sum;
}
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;rt=0;cnt=0;
		while(y){
			vis[t]=y&1;
			if(y&1) s++;
			y>>=1;t++;
		}
		y=(1<<s)-1;
//		printf("%lld\n",y);
		for(int i=1;i<=n;i++){
			scanf("%lld%lld",&l,&r);
			if(r-l+1>x){
//				printf("0 %d\n",y);
				change(rt,0,y,0,y);
				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++;
				}
			}
//			printf("%lld %lld\n",a,b);
			if(a<=b) change(rt,0,y,a,b);
			else change(rt,0,y,0,a),change(rt,0,y,b,y);
		}
		printf("%lld\n",T[rt].sum);
	}
	return 0;
}