#include <iostream>
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
using namespace std;
int main(){
	int n;
	cin >> n;
	FOR(i,0,n){
		int k;
		cin >> k;
		int l[k];
		int r[k];
		FOR(j,0,k){
			cin >> l[j] >> r[j];
		}
		int c = 0;
		FOR(j,0,k){
			if(l[j] < c-1)l[j] = c-1;
			c--;
			if(l[j] > c) c = l[j];
		}
		FOR(j,0,k){
			if(l[k-j-1] < c-1)l[k-j-1] = c-1;
			c--;
			if(l[k-j-1] > c) c = l[k-j-1];
		}
		int best = 1100000;
		FOR(j,0,k){
			int t = r[j] - l[j];
			if(best > t)best = t;
		}
		cout << "K prechodu reky je treba " << best << " pontonu." << endl;
		
	}
}