#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <list>
#include <algorithm>

using namespace std;

int main() {
	int N, K, minVal, a, b, counter,diff,gertruda;
	list<pair<int, int> > points;
	list<pair<int, int> >::iterator it, fix;
	scanf("%d", &N);
	for (int i = 0; i<N; i++) {
		scanf("%d", &K);
		counter = 1;
		scanf("%d %d", &a, &b);
		minVal = b-a;
		points.push_back(make_pair(a,b));					
		while (!points.empty()) {
			gertruda = minVal-points.size();
			for (int j = 0; (counter<K) && (j < gertruda); j++) {
				scanf("%d %d", &a, &b);
				points.push_back(make_pair(a,b));
				minVal = min(minVal, b-a);
				counter++;					
			}
			fix = it = points.begin();
			it++;
			gertruda = min(minVal, int(points.size()));
			for (int j = 1; j< gertruda; j++, it++) {
				diff = min(abs(it->second - fix->first), abs(it->first - fix->second));
				minVal = min(minVal, diff+j);
			}
			points.pop_front();
		}
		printf("K prechodu reky je treba %d pontonu.\n",minVal);
		points.clear();		
	}
	return 0;
}