#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
const int maxn=1005;
int n,k,l[maxn],r[maxn],a[maxn];
ll ans;

int dp[maxn][3][3];
int solve(int n,int k){
    if(k==1){
        bool all0=true;
        for(int i=1;i<=n;i++)if(a[i]!=0){all0=false;break;}
        if(all0)return 0;
        if(n==3&&a[1]==1&&a[2]==1&&a[3]==1)return 0;
    }
    memset(dp,inf,sizeof(dp));
    dp[1][0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=2;j++)
            for(int k=0;k<=2;k++){
                if(dp[i][j][k]>100)continue;
                for(int kk=0;kk<=2;kk++){
                    int val=a[i]-j-k-kk;
                    int need=val<0?-val:(val==1);
                    for(int jj=k;jj<=min(2,j+k);jj++)
                        dp[i+1][jj][kk]=min(dp[i+1][jj][kk],dp[i][j][k]+need);
                }
            }
    return dp[n+1][0][0]<=k;
}

void dfs(int cur){
    if(cur==n+1){
        ans+=solve(n,k);
        return;
    }
    for(a[cur]=l[cur];a[cur]<=r[cur];a[cur]++)
        dfs(cur+1);
}

int main(){int _o;
    for(cin>>_o;_o--;){
        cin>>n>>k;
        for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
        if(n<=5){
            ans=0;
            dfs(1);
            cout<<ans<<endl;
            continue;
        }else{
            for(int i=1;i<=n;i++)a[i]=l[i];
            cout<<solve(n,k)<<endl;
        }
    }
    return 0;
}