#include <iostream>
#include <cmath>

using namespace std;

int main (void) {
    long int n, k, x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> k;
        long int body[k][2];
        long int dist;
        for (int j = 0; j < k; j++) {
            cin >> body[j][0];
            cin >> body[j][1];
        }
        x = abs(body[0][0]-body[0][1]);
        for (int a = 0; a < k; a++)
        {
            dist = abs(body[a][0]-body[a][1]);
            int up = a - (dist - 1);
            if (up < 0) up = 0;
            int dw = a + (dist - 1);
            if (dw >= k) dw = k - 1;
            for (int b = up; b <= dw; b++)
            {
                if (abs(body[a][0]-body[b][1])+abs(a-b)< x)
                    x = abs(body[a][0]-body[b][1])+abs(a-b);
            }
        }


        cout << "K prechodu reky je treba " << x << " pontonu." << endl;
    }
}