#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <sstream>

using namespace std;

#define fore(i, l, r) for(int i = (l); i < (r); ++i)
#define forn(i, n) fore(i, 0, n)
#define fori(i, l, r) fore(i, l, (r) + 1)
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define X first
#define Y second

#if ( _WIN32 || __WIN32__ )
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<typename T> T abs(T a) { return a < 0 ? -a : a; }
template<typename T> T sqr(T a) { return a*a; }

const int INF = (int)1e9;
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932384626433832795;

/*

    This is just to check correctness of input

*/
void ensure(bool value){
    if(!value){
        fprintf(stderr, "Assertion failed");
        throw;
    }
}
void ensure(bool value, string message){
    if(!value){
        fprintf(stderr, "Assertion failed. Message = %s", message.c_str());
        throw;
    }
}
int readInt(int l, int r){
    int x;
    if(scanf("%d", &x) != 1){
        fprintf(stderr, "Expected int in range [%d, %d], but haven't found!", l, r);
        throw;
    }
    if(!(l <= x && x <= r)){
        fprintf(stderr, "Expected int in range [%d, %d], but found %d!", l, r, x);
        throw;
    }
    return x;
}
int readInt(int l, int r, string name){
    int x;
    if(scanf("%d", &x) != 1){
        fprintf(stderr, "Expected int %s in range [%d, %d], but haven't found!", name.c_str(), l, r);
        throw;
    }
    if(!(l <= x && x <= r)){
        fprintf(stderr, "Expected int %s in range [%d, %d], but found %d!", name.c_str(), l, r, x);
        throw;
    }
    return x;
}
li readLong(li l, li r){
    li x;
    if(scanf(LLD, &x) != 1){
        fprintf(stderr, "Expected long long in range ["LLD", "LLD"], but haven't found!", l, r);
        throw;
    }
    if(!(l <= x && x <= r)){
        fprintf(stderr, "Expected long long in range ["LLD", "LLD"], but found "LLD"!", l, r, x);
        throw;
    }
    return x;
}
li readLong(li l, li r, string name){
    li x;
    if(scanf(LLD, &x) != 1){
        fprintf(stderr, "Expected long long %s in range ["LLD", "LLD"], but haven't found!", name.c_str(), l, r);
        throw;
    }
    if(!(l <= x && x <= r)){
        fprintf(stderr, "Expected long long %s in range ["LLD", "LLD"], but found "LLD"!", name.c_str(), l, r, x);
        throw;
    }
    return x;
}
const ld __EPS__ = 1e-15;
ld readDouble(double l, double r){
    double x;
    if(scanf("%lf", &x) != 1){
        fprintf(stderr, "Expected double in range [%lf, %lf], but haven't found!", l, r);
        throw;
    }
    if(!(l <= x + __EPS__ && x <= r + __EPS__)){
        fprintf(stderr, "Expected double in range [%lf, %lf], but found %lf!", l, r, x);
        throw;
    }
    return x;
}
ld readDouble(double l, double r, string name){
    double x;
    if(scanf("%lf", &x) != 1){
        fprintf(stderr, "Expected double %s in range [%lf, %lf], but haven't found!", name.c_str(), l, r);
        throw;
    }
    if(!(l <= x + __EPS__ && x <= r + __EPS__)){
        fprintf(stderr, "Expected double %s in range [%lf, %lf], but found %lf!", name.c_str(), l, r, x);
        throw;
    }
    return x;
}
const int __MAXBUF__ = (int)1e7;
char __buf__[__MAXBUF__];
string readString(char lfc, char rgc, int lfn, int rgn){
    ensure(scanf(" %s ", __buf__) == 1, "Expected string, haven't found");
    string ans = __buf__;
    ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String have incorrect length");
    forn(i, sz(ans))
        ensure(lfc <= ans[i] && ans[i] <= rgc, "String contains incorrect characters");
    return ans;
}
string readString(string pat, int lfn, int rgn){
    ensure(scanf(" %s ", __buf__) == 1, "Expected string, haven't found");
    string ans = __buf__;
    ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String have incorrect length");
    forn(i, sz(ans))
        ensure(find(all(pat), ans[i]) != pat.end(), "String contains incorrect characters");
    return ans;
}
string readString(char lfc, char rgc, int lfn, int rgn, string name){
    ensure(scanf(" %s ", __buf__) == 1, "Expected string " + name + ", haven't found");
    string ans = __buf__;
    ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String " + name + " have incorrect length");
    forn(i, sz(ans))
        ensure(lfc <= ans[i] && ans[i] <= rgc, "String " + name + " contains incorrect characters");
    return ans;
}
string readString(string pat, int lfn, int rgn, string name){
    ensure(scanf(" %s ", __buf__) == 1, "Expected string " + name + ", haven't found");
    string ans = __buf__;
    ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String " + name + " have incorrect length");
    forn(i, sz(ans))
        ensure(find(all(pat), ans[i]) != pat.end(), "String " + name + " contains incorrect characters");
    return ans;
}
string readLine(char lfc, char rgc, int lfn, int rgn){
    ensure(gets(__buf__) != NULL, "Line expected, haven't found");
    string ans = __buf__;
    ensure(lfn <= sz(ans) && sz(ans) <= rgn, "Line have incorrect length");
    forn(i, sz(ans))
        ensure(lfc <= ans[i] && ans[i] <= rgc, "Line contains incorrect characters");
    return ans;
}
string readLine(string pat, int lfn, int rgn){
    ensure(gets(__buf__) != NULL, "Line expected, haven't found");
    string ans = __buf__;
    ensure(lfn <= sz(ans) && sz(ans) <= rgn, "Line have incorrect length");
    forn(i, sz(ans))
        ensure(find(all(pat), ans[i]) != pat.end(), "Line contains incorrect characters");
    return ans;
}
string readLine(){
    ensure(gets(__buf__) != NULL, "Line expected, haven't found");
    string ans = __buf__;
    return ans;
}
char readChar(){
    char c;
    ensure(scanf(" %c ", &c) == 1, "Non-whitespace character expected");
    return c;
}
char readWChar(){
    int ans = getchar();
    ensure(ans != EOF, "Character expected");
    return (char)ans;
}

bool cmp(const pt& a, const pt& b){
    return a.Y < b.Y;
}

void solve_case(){
    int n = readInt(1, 200, "n");
    int x = readInt(1, n, "x");
    vector<pt> a(n);
    vector<int> sep;
    forn(i, n){
        a[i].X = readInt(1, 1000000000, "s[i]");
        a[i].Y = readInt(1, 1000000000, "e[i]");
        ensure(a[i].X <= a[i].Y, "s[i] <= e[i]");
        sep.pb(a[i].X);
        sep.pb(a[i].Y + 1);
    }
    sort(all(sep));
    sep.erase(unique(all(sep)), sep.end());
    
    vector<int> c(sz(sep)), used(sz(sep)), usedman(n);
    forn(i, sz(a)){
        int it = lower_bound(all(sep), a[i].X) - sep.begin();
        while(it < sz(sep) && sep[it] <= a[i].Y){
            c[it]++;
            it++;
        }
    }
    
    sort(all(a), cmp);
    
    assert(c.back() == 0);
    
    int ans = 0;
    forn(i, sz(c) - 1){
        if(c[i] >= x && used[i] < c[i] - x + 1){
            int want = c[i] - x + 1 - used[i];
            vector<int> ok;
            forn(j, sz(a)){
                if((a[j].X <= sep[i] && sep[i] <= a[j].Y) && !usedman[j]){
                    ok.pb(j);
                }
            }
            reverse(all(ok));
            
            assert(!ok.empty());
            assert(sz(ok) >= want);
            forn(j, want){
                int id = ok[j];
                forn(k, sz(c) - 1){
                    if((a[id].X <= sep[k] && sep[k] <= a[id].Y)){
                        used[k]++;
                    }
                }
                usedman[id] = 1;
            }
            ans += want;
        }
    }
    cout << ans << endl;
}

int main(){
#ifdef ssu1
    freopen("input.txt", "rt", stdin);
#endif
    
    int T = readInt(1, 100, "T");
    forn(Ti, T){
        solve_case();
    }
    
    return 0;
}