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


using namespace std;

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


int main(){
	unsigned int N;
	unsigned long K;
	unsigned int min = 1000000;
	unsigned int valLeft;
	unsigned int valRight;
	
	scanf("%u", &N);
	
	while(N){
		scanf("%lu", &K);
		list<Pair> leftMax;
		list<Pair> rightMin;
		
		scanf("%u %u", &valLeft, &valRight);
		leftMax.push_front(Pair(0, valLeft));
		rightMin.push_front(Pair(0, valRight));
		
		min = valRight - valLeft;
		
		for(unsigned long i = 1; i < K; ++i){
			scanf("%u %u", &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){
				unsigned int diff = abs(itRight->value - itLeft->value) + abs(itRight->index - itLeft->index);
				if(diff < min)
					min = diff;
			}

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




	return 0;

}