#include <stdio.h>

#include <vector>

using namespace std;

void process() {
	int n;
	scanf("%d", &n);
	int a,b;
	int leftmax = -1;
	int leftmin = 1000001;
	int rightmin = 1000001;
	int rightmax = -1;
	
	vector<int> leftmaxes;
	vector<int> leftmins;
	vector<int> rightmins;
	vector<int> rightmaxes;
	
	for(int i =0; i <n;i++) {
		scanf("%d%d", &a, &b);	
		//printf("%d %d \n", a,b);
		if(a > leftmax) {
			leftmaxes.clear();
			leftmaxes.push_back(i);
			leftmax = a;
		}
		if(a < leftmin) {
			leftmins.clear();
			leftmins.push_back(i);
			leftmin = a;
		}
		if (a == leftmax) {
			leftmaxes.push_back(i);
		}
		if (a == leftmin) {
			leftmins.push_back(i);
		}
		if(b < rightmin) {
			rightmins.clear();
			rightmins.push_back(i);
			rightmin = b;
		}
		if(b > rightmax) {
			rightmaxes.clear();
			rightmaxes.push_back(i);
			rightmax = b;
		}
		if (b == rightmin) {
			rightmins.push_back(i);
		}
		if (b == rightmax) {
			rightmaxes.push_back(i);
		}
	}
	
	int hor1 = rightmin - leftmax;
	int ver1 = 10000001;
	
	int hor2 = leftmin - rightmax ;
	int ver2 = 10000001;
	
	//printf("%d %d\n", rightmax,leftmin);
	
	for(int i = leftmaxes.size()-1; i>=0; i--) {
		for(int j = rightmins.size()-1; j>=0; j--) {
			int diff = leftmaxes[i] - rightmins[j];
			if(diff < 0)
				diff *= -1;
			
			if(diff < ver1)
				ver1 = diff;
		}
	}
	if(ver1 <0)
		ver1 = 0;
	if(hor1 <0)
		hor1 = 0;
	
	
	for(int i = leftmins.size()-1; i>=0; i--) {
		for(int j = rightmaxes.size()-1; j>=0; j--) {
			int diff = leftmins[i] - rightmaxes[j];
			if(diff < 0)
				diff *= -1;
			
			if(diff < ver2)
				ver2 = diff;
		}
	}
	
	if(ver2 <0)
		ver2 = 0;
	if(hor2 <0)
		hor2 = 0;
	
	int res1 = ver1 + hor1;
	int res2 = ver2 + hor2;
	
	//printf("%d %d %d %d\n", ver1, hor1, ver2, hor2);
	
	printf("K prechodu reky je treba %d pontonu.\n",  res1 < res2 ? res1 : res2);
	
}

int main() {
	
	int n;
	scanf("%d", &n);
	
	for(int i =0; i <n;i++) {
		process();
	}
	
	
	return 0;
}