#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define REP(i, N) for(int (i)=0; (i)<(N); (i)++)
#define ll long long
#define mp make_pair
#define pb push_back
#define INF (1<<30)
int A[11111111], B[11111111];
int instack[1111111];

int main() {
	int N;
	scanf("%d", &N);
	REP(testc, N) {
		memset(instack, -1, sizeof(instack));
		int K;
		scanf("%d", &K);
		REP(i, K) {
			scanf("%d %d", A+i, B+i);
		}
		vector< pair<int, int > > str;
		str.pb(mp(B[0]-A[0], 0));
		for(int i = 1; i < K; i++) {
			int d = B[i]-A[0]+i;
			if(!str.empty() && mp(d, i) >= str.back()) {
				str.pb(mp(d, i));
				instack[i] = str.size()-1;
			} else {
				while(!str.empty() && mp(d, i) < str.back()) {
					instack[str.back().second] = -1;
					str.pop_back();
				}
				str.pb(mp(d, i));
				instack[i] = str.size()-1;
			}
		}
//		REP(i, str.size()) {
//			printf("stack: dist %d, index %d\n", str[i].first, str[i].second);
//		}
		int ans = INF;
		int minhorni = INF;
		int minpos = 0;
		while(instack[minpos] == -1) minpos++;
		for(int i = 0; i < K; i++) {
			int diff = A[0]-A[i];
			if(str[instack[minpos]].first-i+diff < ans) {
				ans = str[instack[minpos]].first-i+diff;
			}
//			printf("da = %d str: %d, %d, i=%d, %d\n", diff, str[instack[minpos]].first, minpos, i, instack[i]);
			ans = min(ans, minhorni);
			if(instack[i] >= 0) {
				int minhorni = min(minhorni, str[instack[i]].first);
				minhorni++;
				instack[i] = -1;
				while(instack[minpos] == -1) {
					minpos++;
				}
			}
		}
		printf("K prechodu reky je treba %d pontonu.\n", ans);
	}
	return 0;
}