#include <stdio.h>

using namespace std;

int bestA, bestB, minimum, i, a, b, length, tcount, tcase, diff;

int main(int argc, char **argv) {
    scanf("%d", &tcount);

    for(tcase=0; tcase<tcount; tcase++) {
        scanf("%d", &length);

        bestA = 0;
        bestB = 1000000;

        minimum = 1000000;

        for(i=0; i<length; i++) {
            scanf("%d %d", &a, &b);

            if(a > bestA) {
                bestA = a;
            }
            if(b < bestB) {
                bestB = b;
            }

            diff = bestB-bestA;
            if(diff < 0) {
                diff = 0;
            }

            if(diff < minimum) {
                minimum = diff;
            }

            --bestA;
            ++bestB;

            if(minimum <= 0) {
                break;
            }
        }

        printf("K prechodu reky je treba %d pontonu.\n", minimum);
    }

    return 0;
}