#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, N) for(int i=0;i<(N);++i)
#define FOR(i, a, b) for(int i=(a);i<=(b);++i)
#define FORI(i, a, b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i=(b)-1;i>=(a);--i)

#define MAX 120000
int K,N;
int A[MAX], B[MAX];
int G[MAX];
int S[MAX];

bool mensi(int a, int b) {
	return G[a] < G[b];
}

int dist(int a, int b, int * C, int *D) {
	return abs(C[a] - D[b]) + abs(a - b);
}

int solve2(int * X, int * Y) {	
	int val = 1000000000;
	REP(i,K) {
		G[i] = dist(i,0,X,Y);
	}	
	REP(i,K) S[i] = i;
	sort(S,S+K,mensi);
	int coo = 0, r = S[coo];
	//printf("HERE");
	REP(p,K) {
		while (p > r && coo < K) {
			coo++;
			r = S[coo];
		}
		if (coo == K) r = K-1;
		val = min(val, dist(r,p,X,Y));
		//printf("TT %d %d %d\n", r, p, dist(r,p,X,Y));
	}
	return val;
}

void solve(){
	scanf("%d", &K);
	int reseni = 0;

	REP(k,K) {
		scanf("%d%d", &A[k], &B[k]);
	}
	reseni = min(solve2(A,B), solve2(B,A));
	printf("K prechodu reky je treba %d pontonu.\n", reseni);
}

int main(){
	scanf("%d", &N);
	REP(n,N){
		solve();
	}
	
	return 0;
}