#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <cstring>
#include <cmath>
#include <deque>
#include <algorithm>

using namespace std;

typedef long long int lint;
typedef long long ll;

long long dx[] = {1,0,-1,0};
long long dy[] = {0,1,0,-1};

struct usecka{
		pair<ll, ll> a;
		pair<ll, ll> b;
	};

ll vzdial(pair<ll, ll>& a, pair<ll, ll>& b){
		return abs(a.first - b.first) + abs(a.second - b.second);
	}

ll skus(vector<pair<ll,ll> >& pole){
		pair<ll, ll> naj = make_pair(pole[0].second, 0);
		ll min_vzd = pole[0].second - pole[0].first;
		pair<ll, ll> akt, lepsi;
		for(int i = 1; i < pole.size(); i++){
				akt.second = i;
				akt.first = pole[i].first;
				lepsi = make_pair(pole[i-1].second, i-1);
				if(vzdial(akt,lepsi) <= vzdial(akt, naj)){
						naj = lepsi;
					}
				min_vzd = min(min_vzd, vzdial(naj, akt));
				min_vzd = min(min_vzd, pole[i].second - pole[i].first);				
			}
		return min_vzd;
	}

int main()
{
	lint n;
	scanf("%lld",&n);
	while(scanf("%lld",&n) == 1){
			ll a,b;
			vector<pair<ll,ll> > pole;
			while(n--){
					scanf("%lld%lld", &a, &b);
					pole.push_back(make_pair(a,b));
				}
			ll naj = skus(pole);
			reverse(pole.begin(), pole.end());
			naj = min(skus(pole), naj);
			printf("K prechodu reky je treba %lld pontonu.\n", naj);
		}
}