#include<iostream>
using namespace std;

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

int dist(int x1, int y1, int x2, int y2) {
	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 y1=0, y2=0, x1=0, x2=1000000, dim = 1000000;
		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";
			}
*/
// } dbg
			int d1 = dist(a,y, b, y);
			int d2 = dist(a,y,x2,y2);
			int d3 = dist(x1,y1,b,y);

			if (d1 <= dim && d1<=d2 && d1<=d3) {
				x1 = a;
                                y1 = y;
				x2 = b;
				y2 = y;
				dim = dist(x1,y1,x2,y2);
//				cout << " #1 ("<<dim<<") ";
			}
			if (d2 <= dim && d2<=d1 && d2<=d3) {
				x1 = a;
				y1 = y;
				dim = dist(x1,y1,x2,y2);
//				cout << " #2 ";
			}
			if (d3 <= dim && d3<=d1 && d3<=d2) {
                                x2 = b;
                                y2 = y;
				dim = dist(x1,y1,x2,y2);
//				cout << " #3 ";
			}

//			cout << y << " "<< x1<<","<<y1 << " " << x2<<","<<y2<< " " <<dim<< endl;
			++ y;
		}
		cout << "K prechodu reky je treba " << (dim) << " pontonu."<< endl;
	}
	return 0;
}