#include <cstdio>
#include <cstdlib>

#include <set>
#include <map>

#define setmin( m, a ) m = a < m ? a : m;

void solveCase() {
    int K, A, B, m, t;

    scanf( "%d", &K );

    std::map<int,int> Alist, Blist;
    std::map<int,int>::iterator it;
    std::map<int,int>::reverse_iterator itr;

    scanf( "%d %d", &A, &B );
    m = B-A;
    Alist[ A ] = 0;
    Blist[ B ] = 0;
    for( int i = 1; i < K; i++ ) {
        scanf( "%d %d", &A, &B );
        t = B-A;
        if ( t < m )
            m = t;
        itr = Alist.rbegin();
        t = B - (itr->first - i);
        while( t <= 0 ) {
            t = i - itr->second;
            setmin( m, t );
            itr++;
            t = B - (itr->first - i);
        }
        if( t < m ) 
            m = t;
        it = Blist.begin();
        t = it->first + i - A;
        while( t <= 0 ) {
            t = i - it->second;
            setmin( m, t );
            it++;
            t = it->first + i - A;
        }
        if( t < m )
            m = t;
        Alist[ A+i ] = i;
        Blist[ B-i ] = i;
    }
    printf( "K prechodu reky je treba %d pontonu.\n", m );
}

int main(int argc, char **argv) {
    int N;
    scanf("%d", &N );
    while( N-- ) {
        solveCase();
    }
    return 0;
}