#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

int main(void)
{
	int n;
	scanf(" %d ", &n);
	
	for(int i = 0; i < n; i++)
	{
		vector<int> left, right;
		
		int lines;
		scanf(" %d ", &lines);
		
		int maxL = 0, minR = 1000000;
		int lPos = 0, rPos = 0;
		
		for(int j = 0; j < lines; j++)
		{
			int a, b;
			scanf(" %d %d ", &a, &b);
			
			left.push_back(a);
			right.push_back(b);
			
			if(a > maxL) { lPos = j; maxL = a; }
			if(b < minR) { rPos = j; minR = b; }
		}
		
		//cout << lPos << " " << maxL << " " << rPos << " " << minR;
		
		int minLength = -1;
		
		for(int j = 0; j < lines; j++)
		{
			int rVal = right[j];
			
			int length = (rVal - maxL) + (j > lPos ? j - lPos : lPos - j);
			if(minLength == -1 || length < minLength) minLength = length;
		}
		
		for(int j = 0; j < lines; j++)
		{
			int lVal = left[j];
			
			int length = (minR - lVal) + (j > rPos ? j - rPos : rPos - j);
			if(minLength == -1 || length < minLength) minLength = length;
		}
		
		cout << "K prechodu reky je treba " << minLength << " pontonu." << endl;
	}
	
	return 0;
}