#include<bits/stdc++.h>
#define M 6005
#define LL long long
using namespace std;
int n;
struct node{
    int l,r;
}A[M];
int tmp[M],len;
LL dp[2][M];
int main(){
    for(int _=(scanf("%d",&_),_);_;_--){
        scanf("%d",&n);
        len=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&A[i].l,&A[i].r);
            tmp[++len]=A[i].l;
            tmp[++len]=A[i].l-1;
            tmp[++len]=A[i].l+1;
            tmp[++len]=A[i].r;
            tmp[++len]=A[i].r-1;
            tmp[++len]=A[i].r+1;
        }
        sort(tmp+1,tmp+len+1);
        len=unique(tmp+1,tmp+len+1)-tmp-1;

        for(int i=1;i<=n;i++){
            A[i].l=lower_bound(tmp+1,tmp+len+1,A[i].l)-tmp;
            A[i].r=lower_bound(tmp+1,tmp+len+1,A[i].r)-tmp;
        }
        for(int i=1;i<=len;i++)dp[0][i]=2e18;
        for(int i=A[1].l;i<=A[1].r;i++)dp[0][i]=0;
        bool cur=1;
        LL odd,eve;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=len;j++)dp[cur][j]=2e18;
            odd=eve=2e18;
            for(int j=1;j<=len;j++){
                if(tmp[j]&1)odd=min(odd,dp[!cur][j]*2-tmp[j]);   
                else eve=min(eve,dp[!cur][j]*2-tmp[j]);
                if(j>=A[i].l&&j<=A[i].r){
                    if(tmp[j]&1)dp[cur][j]=min(dp[cur][j],min((tmp[j]+odd)/2,(tmp[j]+eve+1)/2));
                    else dp[cur][j]=min(dp[cur][j],min((tmp[j]+odd+1)/2,(tmp[j]+eve)/2));
                }
            }
            odd=eve=2e18;
            for(int j=len;j;j--){
                if(tmp[j]&1)odd=min(odd,dp[!cur][j]*2+tmp[j]);   
                else eve=min(eve,dp[!cur][j]*2+tmp[j]);
                if(j>=A[i].l&&j<=A[i].r){
                    if(tmp[j]&1)dp[cur][j]=min(dp[cur][j],min((odd-tmp[j])/2,(eve-tmp[j]+1)/2));
                    else dp[cur][j]=min(dp[cur][j],min((odd-tmp[j]+1)/2,(eve-tmp[j])/2));
                }
            }
            LL res=2e18;
            for(int j=A[i].l;j<=A[i].r;j++)res=min(res,dp[cur][j]);
            cur^=1;
        }
        LL ans=2e18;
        for(int i=A[n].l;i<=A[n].r;i++)ans=min(ans,dp[!cur][i]);
        printf("%I64d\n",ans);
    }
    return 0;
}