#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <queue>

using namespace std;
#define FOR(i,j) for(int i = 0; i < j; i++)
int main(void){
	int n, l, r, lines, l_max, k_l_max, r_min, k_r_min, best_down, new_best_down, best_up, new_best_up, best;

	scanf(" %d",&n);
	FOR(i,n) {
		scanf(" %d", &lines);
		l_max = 0;
		r_min = 1000000;
		k_l_max = 0;
		k_r_min = 0;
		best_up = 1000000;
		best_down = 1000000;

		FOR(k,lines) {
			scanf(" %d%d", &l, &r);
			if (l + k > l_max + k_l_max) {
				l_max = l;
				k_l_max = k;
			}
			if (k-r > k_r_min - r_min) {
				r_min = r;
				k_r_min = k;
				}

			new_best_down = r > l_max ? r-l_max+k-k_l_max : k-k_l_max;
			if (new_best_down < 0)
				new_best_down = 0;
			best_down = min(new_best_down, best_down);

			new_best_up = r_min > l ? r_min-l+k-k_r_min : k-k_r_min;
			if (new_best_up < 0)
				new_best_up = 0;
			best_up = min(new_best_up , best_up);
		}

		best = min(best_up,best_down);
		
		printf("K prechodu reky je treba %d pontonu.\n", best);
	}


	return 0;
}