#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <list>
#include <cmath>


using namespace std;

struct Pair{
	long int index;
	long int value;
	Pair(long ind, long val):index(ind), value(val){}
};


int main(){
	long int N;
	long int K;
	long int min = 1000000;
	long int valLeft;
	long int valRight;
	
	scanf("%ld", &N);
	
	while(N){
		scanf("%ld", &K);
		list<Pair> leftMax;
		list<Pair> rightMin;
		
		scanf("%ld %ld", &valLeft, &valRight);
		leftMax.push_front(Pair(0, valLeft));
		rightMin.push_front(Pair(0, valRight));
		
		min = valRight - valLeft;
		
		for(long int i = 1; i < K; ++i){
			scanf("%ld %ld", &valLeft, &valRight);
			//if(valLeft > leftMax.front().value){
			//	leftMax.clear();
				leftMax.push_front(Pair(i, valLeft));
			//}
			//else if(valLeft == leftMax.front().value)
			//	leftMax.push_front(Pair(i, valLeft));
			
			if(min > valRight - valLeft)
				min = valRight - valLeft;
			//if(valRight < rightMin.front().value){
			//	rightMin.clear();
			//	rightMin.push_front(Pair(i, valRight));
			//}
			//else if(valRight == rightMin.front().value)
				rightMin.push_front(Pair(i, valRight));
		}
		
		
		
		for(list<Pair>::const_iterator itLeft = leftMax.begin(); itLeft != leftMax.end(); ++itLeft){
			for(list<Pair>::const_iterator itRight = rightMin.begin() ; itRight != rightMin.end(); ++itRight){
				long diff = abs(itRight->value - itLeft->value) + abs(itRight->index - itLeft->index);
				if(diff < min){
					//cout<<"min = "<<min<<" diff=" << diff << endl;
					min = diff;
					//cout<<itRight->value <<"-"<<itLeft->value<<"+"<<itRight->index<< "-" <<itLeft->index<<endl;
				}
			}

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




	return 0;

}