#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for ( int i = int(a); i <= int(b); ++i )
#define FORD(i,a,b) for ( int i = int(a); i >= int(b); --i )
#define REP(i,n) for ( int i = 0; i < int(n); ++i )
using namespace std;
#define INF 500000000

int main( ) {
	ios::sync_with_stdio( 0 );
  int t,n;
  int bl, br, best, row;
  int b1, b2, b3, b4;
	int l, r, prevL, prevR, rRow, lRow;
  cin >> t;
  while ( t--) {
		cin >> n;
		best = prevR = INF;
		prevL = rRow = lRow = -INF;
		bl = -INF;
		br = INF;
		REP( i, n ) {
			cin >> l >> r;
			/*cout << "l: " << l << ", r: " << r << " " << endl;
			cout << "prevL:" << prevL << ", lRow: " << lRow << endl;
			cout << "prevR:" << prevR << ", rRow: " << rRow << endl;*/
			best = min( best, r - l );
			//cout << "best: " << best << endl;
			if ( prevR < l )
				best = min( best, i - rRow - 1 );
			else
				best = min( best, prevR + (i - rRow) - l );
			if ( prevL > r )
				best = min( best, i - lRow - 1 );
			else
				best = min( best, r + (i - lRow) - prevL );
			if ( l >= prevL - (i - lRow ) ) {
				lRow  = i;
				prevL = l;
			}
			if ( r <= prevR - ( i - rRow ) ) {
				rRow  = i;
				prevR = r;
			}
		}
		cout << "K prechodu reky je treba " << best << " pontonu." << endl;
	}
	return 0;
}