#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int A[1010], B[1010], n;

int F[6010], G[6010];

int Abs(int x) {x = x < 0 ? -x : x; return (x + 1) / 2;}

int Solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d", &A[i], &B[i]);
    vector <int> V(1, -1);
    for(int i = 1; i <= n; i++) V.push_back(A[i]), V.push_back(B[i]), V.push_back(A[i] - 1), V.push_back(A[i] + 1), V.push_back(B[i] - 1), V.push_back(B[i] + 1);
    sort(V.begin(), V.end()), V.resize(unique(V.begin(), V.end()) - V.begin());
    for(int i = 1; i <= n; i++) {
        A[i] = lower_bound(V.begin(), V.end(), A[i]) - V.begin();
        B[i] = lower_bound(V.begin(), V.end(), B[i]) - V.begin();
    }
    memset(F, 63, sizeof F);
    int t = (int) V.size() - 1;
    for(int i = A[1]; i <= B[1]; i++) F[i] = 0;
    for(int i = 2; i <= n; i++) {
        memcpy(G, F, sizeof F);
        int mx1 = -1e9, mx2 = -1e9;
        memset(F, 63, sizeof F);
        for(int j = 1; j <= B[i]; j++) {
            if(V[j] % 2 == 1) mx1 = max(mx1, -G[j] + V[j] / 2); else mx2 = max(mx2, -G[j] + V[j] / 2);
            if(A[i] <= j) {
                if(V[j] % 2 == 1) F[j] = min(V[j] / 2 - mx1, V[j] / 2 - mx2 + 1);
                else F[j] = min(V[j] / 2 - mx2, V[j] / 2 - mx1);
            }
        }
        int mn1 = 1e9, mn2 = 1e9;
        for(int j = t; j >= A[i]; j--) {
            if(V[j] % 2 == 1) mn1 = min(mn1, G[j] + V[j] / 2); else mn2 = min(mn2, G[j] + V[j] / 2);
            if(B[i] >= j) {
                if(V[j] % 2 == 1) F[j] = min(F[j], min(mn1 - V[j] / 2, mn2 - V[j] / 2));
                else F[j] = min(F[j], min(mn2 - V[j] / 2, mn1 - V[j] / 2 + 1));
            }
        }
    }
    int ans = 1e9;
    for(int i = 1; i <= t; i++) ans = min(ans, F[i]);
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        printf("%d\n", Solve());
    }
}