#include <stdio.h>
#include <stdlib.h>


int k, res;
int **border;

void left(){
	int i;
	for (i = 0; i < k;i++){
		border[0][i]++;
	}
}

void right(){
	int i;
	for (i = 0; i < k;i++){
		border[0][i]--;
	}
}

int down(int er){
	int i;
	int tmp = border[0][k-1];
	for (i = k-1; i > 0;i--){
		border[0][i] = border[0][i-1];
	}
	border[0][0] = er;
	return tmp;
}

int up(int tmp){
	int i;
	int foo = border[0][0];
	for (i = 0; i < (k-1);i++){
		border[0][i] = border[0][i+1];
	}
	border[0][k-1] = tmp;
	return foo;
}

void check(int stage){
	int i;
	for (i = 0; i < k; i++){
		if (border[0][i] == border[1][i]){
			res = stage;
		}
		if (i < (k-1) && (border[0][i] > border[1][i+1])){
			res = stage;
		}
		if (i > 0 && (border[0][i] > border[1][i-1])){
			res = stage;
		}
	}
}

void move(int stage){
	int tmp;
	if (stage >= res) return;
	stage++;
	left();
	check(stage);
	move(stage);
	right();

	tmp = down(0);
	check(stage);
	move(stage);
	up(tmp);

	tmp = up(0);
	check(stage);
	move(stage);
	down(tmp);

	
	
}

int main(){
	int t_c, i;
	scanf("%d", &t_c);
	while(t_c!= 0){
		res = 1000000;
		scanf("%d",&k);
		border =(int **) malloc(sizeof(int *)*2);
		border[0] = (int *) malloc(sizeof(int)*k);
		border[1] = (int *) malloc(sizeof(int)*k);
		for (i = 0; i < k; i++){
			scanf("%d %d", &border[0][i], &border[1][i]);
			if (border[1][i] - border[0][i] < res){
				res = border[1][i] - border[0][i];
			}
		}
		move(0);
		printf("K prechodu reky je treba %d pontonu.\n", res);
		free(border[0]);
		free(border[1]);
		free(border);
		t_c--;
	}
	return 0;
}