#include <stdio.h>

static inline int max(int a, int b) {
	if ( a > b ) return a;
	return b;
}

static inline int min(int a, int b) {
	if ( a < b ) return a;
	return b;
}

int main() {

	int * s1;
	int * s2;
	int * e1;
	int * e2;
	int * s;
	int * e;

	s1 = malloc(10000000 * sizeof(int));
	s2 = malloc(10000000 * sizeof(int));
	e1 = malloc(10000000 * sizeof(int));
	e2 = malloc(10000000 * sizeof(int));
	s = malloc(10000000 * sizeof(int));
	e = malloc(10000000 * sizeof(int));

	int n;
	scanf("%d", &n);
	int i;

	for ( i = 0; i < n; ++i ) {
		int k;
		scanf("%d", &k);
		int j;
		for ( j = 0; j < k; ++j )
			scanf("%d %d", &s[j], &e[j]);
		s1[0] = s[0];
		s2[k-1] = s[k-1];
		e1[0] = e[0];
		e2[k-1] = e[k-1];
		for ( j = 1; j < k; ++j )
			s1[j] = max(s[j], max(s[j-1]-1, s1[j-1]-1));
		for ( j = k-2; j >= 0; --j )
			s2[j] = max(s[j], max(s[j+1]-1, s2[j+1]-1));
		for ( j = 1; j < k; ++j )
			e1[j] = min(e[j], min(e[j-1]+1, e1[j-1]+1));
		for ( j = k-2; j >= 0; --j )
			e2[j] = min(e[j], min(e[j+1]+1, e2[j+1]+1));
		int m = e1[0]-s1[0];
		for ( j = 0; j < k; ++j ) {
			int m1 = max(s1[j], s2[j]);
			int m2 = min(e1[j], e2[j]);
			if ( m > m2-m1 )
				m = m2-m1;
		}
		printf("K prechodu reky je treba %d pontonu.\n", m);
	}
	return 0;

}