#include <iostream>
#include <list>

typedef unsigned int uint;
struct Line {
	uint left, right, top;
};

int main() {
	std::list<Line> lines;
	uint nLines;
	
	uint nCases;
	std::cin >> nCases;
	
	for (uint iCase = 0; iCase < nCases; ++iCase)
	{
		uint size;
		std::cin >> size;
		
		lines.clear();
		nLines = 0;
		
		uint min = 0;
		for (uint i = 0; i < size; ++i)
		{
			Line line;
			std::cin >> line.left >> line.right;
			line.top = i;
			if (i == 0)
				min = line.right - line.left;
			lines.push_back(line);
			nLines++;
			for (std::list<Line>::const_reverse_iterator j = lines.rbegin(), jend = lines.rend(); j != jend; ++j)
			{
				const Line& other = *j;
				if (line.right - other.left + line.top - other.top < min)
					min = line.right - other.left + line.top - other.top;
				if (other.right - line.left + line.top - other.top < min)
					min = other.right - line.left + line.top - other.top;
			}
			while (nLines-- > min)
				lines.pop_front();
		}
		
		std::cout << "K prechodu reky je potreba " << min << " pontonu." << std::endl;
	}
	
	return 0;
}