#include <bits/stdc++.h>
#define N 1004
#define mxK 4
using namespace std;
typedef long long ll;

int T, n, K, a[N];
int ans, mx;
bool f[N][mxK][N+mxK][2], pre[N][mxK][N+mxK], suf[N][mxK][N+mxK];

struct Pnt { int l, r; } p[N];

void dfs (int x)
{
    if (x==n+1) {
        memset(f, 0, sizeof(f));
        memset(pre, 0, sizeof(pre));
        memset(suf, 0, sizeof(suf));

        f[0][0][0][0]=1;
        for (int j=0; j<=mx+K; j++) {
            pre[0][0][j]=((j>0 ? pre[0][0][j-1] : 0) || (f[0][0][j][0] || f[0][0][j][1]));
        }
        for (int j=mx+K; j>=0; j--) {
            suf[0][0][j]=(suf[0][0][j+1] || f[0][0][j][0]);
        }

        for (int i=1; i<=n; i++) {
            for (int ksum=0; ksum<=K; ksum++) {
                for (int k=0; k<=ksum; k++) {
                    for (int j=0; j<=a[i]+k; j++) if (j!=a[i]+k-1) {
                        if (j>0) {
                            f[i][ksum][j][1]|=pre[i-1][ksum-k][j-1];
                        }
                        f[i][ksum][j][0]|=suf[i-1][ksum-k][j];
                        f[i][ksum][j][0]|=f[i-1][ksum-k][j][1];
                    }
                }
                for (int j=0; j<=mx+K; j++) {
                    pre[i][ksum][j]=((j>0 ? pre[i][ksum][j-1] : 0) | (f[i][ksum][j][0] | f[i][ksum][j][1]));
                }
                for (int j=mx+K; j>=0; j--) {
                    suf[i][ksum][j]=(suf[i][ksum][j+1] | f[i][ksum][j][0]);
                }
            }
        }

        bool res=0;
        for (int j=0; j<=a[n]+K; j++) { res|=f[n][K][j][0]; }
        ans+=res;

        return;
    }

    for (int i=p[x].l; i<=p[x].r; i++) {
        a[x]=i; dfs(x+1);
    }
}

int main ()
{
    // freopen("stone.in", "r", stdin);
    // freopen("stone.out", "w", stdout);

    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &K);
        ans=0; mx=0;
        for (int i=1; i<=n; i++) {
            scanf("%d %d", &p[i].l, &p[i].r);
            mx=max(mx, p[i].r);
        }
        dfs(1);
        printf("%d\n", ans);
    }

    return 0;
}