#include <stdio.h>

#include <vector>

using namespace std;

void process() {
	int n;
	scanf("%d", &n);
	int a,b;
	int leftmax = -1;
	int rightmin = 1000001;
	
	vector<int> leftmaxes;
	vector<int> rightmins;
	
	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 == leftmax) {
			leftmaxes.push_back(i);
		}
		if(b < rightmin) {
			rightmins.clear();
			rightmins.push_back(i);
			rightmin = b;
		}
		if (b == rightmin) {
			rightmins.push_back(i);
		}
	}
	
	int hor = rightmin - leftmax;
	int ver = 10000001;
	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;
			//printf("%d\n", diff);
			
			if(diff < ver)
				ver = diff;
		}
	}
	if(ver <0)
		ver = 0;
	if(hor <0)
		hor = 0;
	
	printf("K prechodu reky je treba %d pontonu.\n", ver+hor);
	
}

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