#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> pii;

#define PB push_back
#define MP make_pair

#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)

#define MM(co, cim) memset((co), (cim), sizeof((co)))
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;

int myabs ( int a )
{
	return a >= 0 ? a : -a;
}

int mydist ( pii left, pii right )
{
	return abs( left.first - right.first ) + abs( left.second - right.second ) - 1 ;
}

int main ( void )
{
	int N, K, A, B;

	scanf( "%d", &N );

	for ( int n = 0; n < N; n++ ) {
		scanf( "%d", &K );
		
		vector<pii> left, right;
		for ( int k = 0; k < K; k++ ) {
			scanf( "%d %d", &A, &B );
			left.PB( MP( A - 1, k ) );
			right.PB( MP( B, k ) );
		}

		int min = -1;
		for ( unsigned int l = 0; l < left.size(); l++ ) {
			for ( unsigned int r = 0; r < right.size(); r++ ) {
				if ( ( l == 0 && r == 0 ) || ( mydist( left[ l ], right[ r ] ) < min ) ) {
					min = mydist( left[ l ], right[ r ] );
				}
			}
		}

		printf("K prechodu reky je treba %d pontonu.\n", min);
	}
	
	

	return 0;
}