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

int abs(int x) {
	if (x < 0)
		return -x;
	return x;
}

int dist(int x1, int y1, int x2, int y2) {
	if (x1 >= x2)
		return abs(y2-y1) - 1;
	return abs(x2-x1) + abs(y2-y1) -1;
}


int main(int auuuufff, char **bleeeeee) {
        int n;
        cin >> n;
        for (int i = 0 ; i<n ; ++i) {
                unsigned x;
                cin >> x;
		int dim = 1000000;
		int la=0, lb=1000001;
		vector<pair<int, int> > data;

		unsigned y = 0;
		for (unsigned j=0; j<x; ++j) {
			int a,b;
			cin >> a >> b;
			a -= 1;
//dbg {
/*			for (int x = 0; x < 15; ++x) {
				if (x>a && x<b) {
					cout << ".";
				} else
					cout << "X";
			}
			cout << endl;
*/
// } dbg

			if (b < la || a > lb) {
				dim = 0;
				break;
			}
			la = a;
			lb = b;

			int d = dist(a,y, b, y);
			if (d < dim) {
				dim = d;
			}
			data.push_back(make_pair(a,b));
		}

		for (size_t i=0; i<data.size(); ++i) {
			for (size_t j=max<int>(i-dim,0); j<min<int>(i+dim,data.size()); ++j) {
				int d2 = dist(data[i].first, i, data[j].second, j);
				if (d2 < dim) {
					dim = d2;
				}
			}
		}
		cout << "K prechodu reky je treba " << (dim) << " pontonu."<< endl;
	}
	return 0;
}