#include <bits/stdc++.h>
using namespace std;

//#define LOCAL
#define FILE_IO
#define FILE_IO_NAME "lucky"

#define int long long

#ifdef LOCAL
template <typename T>
class safe_vector: public vector<T> {
public:
    using vector<T>::vector;
    typename vector<T>::reference operator [] (const typename vector<T>::size_type index) {
        return this->at(index);
    }
    typename vector<T>::const_reference operator [] (const typename vector<T>::size_type index) const {
        return this->at(index);
    }
};
#define vector safe_vector
#endif // LOCAL

const int INF = 4e18;

struct Range {
    int left;
    int right;
};

struct Operation {
    Range countRange;
    Range numRange;
};

bool byLeft(const Operation &A, const Operation &B) {
    return A.numRange.left < B.numRange.left;
}

bool byRight(const Operation &A, const Operation &B) {
    return A.numRange.right > B.numRange.right;
}

void solve() {
    int n;
    cin >> n;
    vector<Operation> opeartions(n);
    bool spacialB = true;
    for (int i = 0; i < n; i++) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (l1 != r1) {
            spacialB = false;
        }
        opeartions[i].countRange.left = l1;
        opeartions[i].countRange.right = r1;
        opeartions[i].numRange.left = l2;
        opeartions[i].numRange.right = r2;
    }
    int minValue = INF, maxValue = -INF;
    sort(opeartions.begin(), opeartions.end(), byLeft);
    vector<int> restRight(n);
    for (int i = n - 1; i >= 0; i--) {
        restRight[i] = opeartions[i].countRange.left;
        if (i < n - 1) {
            restRight[i] += restRight[i + 1];
        }
    }
    int nowLeft = 0;
    for (int i = 0; i < n; i++) {
        Operation &opeartion = opeartions[i];
        nowLeft += opeartion.countRange.right;
        int total = nowLeft;
        if (i + 1 < n) {
            total += restRight[i + 1];
        }
        if (nowLeft >= (total + 1) / 2) {
            minValue = opeartion.numRange.left;
            break;
        }
    }
    sort(opeartions.begin(), opeartions.end(), byRight);
    for (int i = n - 1; i >= 0; i--) {
        restRight[i] = opeartions[i].countRange.left;
        if (i < n - 1) {
            restRight[i] += restRight[i + 1];
        }
    }
    nowLeft = 0;
    for (int i = 0; i < n; i++) {
        Operation &opeartion = opeartions[i];
        nowLeft += opeartion.countRange.right;
        int total = nowLeft;
        if (i + 1 < n) {
            total += restRight[i + 1];
        }
        if (nowLeft >= (total + 2) / 2) {
            maxValue = opeartion.numRange.right;
            break;
        }
    }
    cout << (maxValue - minValue + 1) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    #ifdef LOCAL
    #ifdef FILE_IO
    if (strcmp(FILE_IO_NAME, "FILE_IO_NAME") == 0) {
        cout << "[error] FILE_IO was defined but FILE_IO_NAME was not set!" << endl;
        return 1;
    }
    #endif // FILE_IO
    freopen("D:\\temp\\test\\" FILE_IO_NAME "\\" FILE_IO_NAME "4.in", "r", stdin);
//    freopen("my.in", "r", stdin);
//    freopen("my.out", "w", stdout);
    #elif defined(FILE_IO) // LOCAL
    freopen(FILE_IO_NAME ".in", "r", stdin);
    freopen(FILE_IO_NAME ".out", "w", stdout);
    #endif // FILE_IO
    int c, T;
    cin >> c >> T;
    while (T--) {
        solve();
    }
    return 0;
}