#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int M=5005*60;
int n,m,x,ans,cnt[65];
vector<int>a[M],rec;
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
void insert(int y,int l){
    a[++m].clear();
    for (int i=60;i>=l;i--)
        a[m].emplace_back((x&y)>>i&1);
}
int query(int x){return x<=60?1ll<<cnt[60-x]:1;};
void solve(){
    n=read();x=read();m=0;
    for (int i=0;i<=60;i++)
        cnt[i]=(i?cnt[i-1]:0)+(x>>i&1);
    for (int i=1;i<=n;i++){
        int l=read(),r=read()+1,lg=31^__builtin_clz(l^r);
        for (int j=0;j<lg;j++)
            if (l>>j&1)
                insert(l,j),l+=1ll<<j;
        for (int j=lg;~j;j--)
            if (~l>>j&1&&r>>j&1)
                insert(l,j),l+=1ll<<j;
    }
    sort(a+1,a+m+1);ans=query(a[1].size());rec=a[1];
    for (int i=2;i<=m;i++){
        bool flag=rec.size()>a[i].size();
        for (int j=0;!flag&&j<rec.size();j++)
            if (a[i][j]&&!rec[j]) {flag=1;break;}
        if (flag) ans+=query(a[i].size()),rec=a[i];
    }
    printf("%lld\n",ans);
}
signed main(){int T=read();while (T--) solve();return 0;}