#include <stdio.h>
#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main (int argc, const char * argv[])
{
	long n;
	scanf("%ld",&n);
	for (long i = 0; i<n; i++)
	{
		long vyska;
		scanf("%ld",&vyska);
		vector<long> leve, prave;
		leve.reserve(vyska);
		prave.reserve(vyska);
		long left, right;
			
		for (long j = 0; j<vyska; j++) // prochazim mapu
		{	
			scanf("%ld%ld",&left,&right);
			leve.push_back(left);	
			prave.push_back(right);	
		}
		
		long min = vyska + 1000001;
		for (long j = 0; j<vyska; j++) // prochazim mapu
		{	
			long k = j;
			long x = 1;
			bool smimOdcitat = 1, smimPricitat = 1, stav = 0;
			if (!j) { smimOdcitat=0; stav=1; }
			while (k > j-min-1 && k < j+min+1) // prochazim mapu
			{	
				if (k!=vyska) {
					long vzdal;
					if (leve[j] > prave[k]) vzdal = abs(k - j)-1; 
					else {vzdal = abs(prave[k] - leve[j]) + abs(k - j); }
	//cout << "j:" << j << "[" << leve[j] << "]" << "k:" << k <<" " << "[" << prave[k] << "]" <<  "vzdal:" << vzdal << " " << min << " long: " << k-min-1 << " " << k+min+1 << endl;
					if (vzdal < min) min = vzdal;
				}
				long old_k = k;
				if ((!stav && smimOdcitat)) { 
					if (!smimPricitat) k-=1; else k-=x; 
				}else{ 
					if (!smimOdcitat) k+=1; else k+=x; 
				}
				if (old_k == 1) { smimOdcitat = 0; stav = 1; }
				else if (old_k == vyska-2) { smimPricitat = 0; stav = 0; }
				else stav=!stav;
				x++;
			}
		}

		printf("K prechodu reky je treba %ld pontonu.\n", min);
	}
	return 0;
}