#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
#define ll long long
#define nl '\n'
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K th element in a set (counting from zero)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int n, h;
        cin >> n >> h;

        vector<ll> v(n, n);
        vector<ll> pr(n + 1, 0);
        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            x--;
            pr[x]++;
            pr[y]--;

        }
        for (int i = 1; i < n; i++)
            pr[i] += pr[i - 1];

        for (int i = 0; i < n; i++) {
            v[i] -= pr[i];
        }

        sort(v.begin(), v.end());

        ll sum = 0;
        for (int i = 0; i < h; i++)
            sum += v[i];

        cout << sum << nl;
    }

    return 0;
}