// zoltan chivay
// marigold
// triss
// MOUDRY MUSTAFA KURVA
// RASTAFARIANI
// hwefgwehbuyhdfbuyegbygwebdhgbyuycygweyhgbcy7wegyecygsdyhedtysdgvbastwvtsdvbetev xdte4vbdyje3h723654y6efhu7fy2e47uj34fg78 34y89y 78924rtvui 34hu89pfgy24 j fu b834uj i834ut8 bu 894ug ergu 8


#include<iostream>
#include<cstdlib>
using namespace std;

int min (int a, int b) {
	return a < b ? a : b;
}

int maxn (int a, int b) {
	return a > b ? a : b;
}

int abs (int a) {
	if (a < 0) return -1*a;
	return a;
}

int testRow (int y, int * pS, int * pC, int minCost, int k) {
	int rowCost = 1000001;
	int refRow = max(0, y - minCost);
	for (; refRow < min(k, y + minCost); refRow++) {
		int cost = pC[refRow] - pS[y] + abs(y-refRow);
		rowCost = min (cost, rowCost);
	}
	return rowCost;
}


int main (int argc, char ** argv) {

int n;
cin >> n;

for (int mustafa = 0; mustafa < n; mustafa++) {
	int k;
	cin >> k;
	
	int * pS = new int[k];
	int * pC = new int[k];
	
	int maxX = -1;
	
	for (int i = 0; i < k; i++) {
		cin >> pS[i];
		cin >> pC[i];
		if (pC[i] > maxX) maxX = pC[i];
	}
	int minCost = 1000001;
	
	for (int y = 0; y < k; y++) {
		int rowCost = testRow (y, pS, pC, minCost, k);
		minCost = min(minCost, rowCost);	
	}
	
	cout << "K prechodu reky je treba " << minCost << " pontonu." << endl;
	delete [] pC;
	delete [] pS;
}

return 0;
}