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


int k, res;
int **border;

int **ld_match, l, d;

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;
		}
	}
}

int valid(int left, int up){
	return (ld_match[left][l+up] == 0);
}

void move(int left_mv, int up_mv){
	int tmp;
	ld_match[left_mv][l+up_mv] = 1;

	if ((left_mv + 1 + abs(up_mv)) < res && valid(left_mv + 1, up_mv)){
		left();
		check(left_mv + 1 + abs(up_mv));
		move(left_mv + 1, up_mv);
		right();
	}

	if ((left_mv + abs(up_mv -1)) < res && valid(left_mv, up_mv - 1)){
		tmp = down(0);
		check(left_mv + abs(up_mv-1));
		move(left_mv, up_mv-1);
		up(tmp);
	}

	if ((left_mv + abs(up_mv+1)) < res && valid(left_mv, up_mv + 1)){
		tmp = up(0);
		check(left_mv + abs(up_mv +1));
		move(left_mv, up_mv+1);
		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];
			}
		}
		l = res+1;
		d = 2*res +1; 
		ld_match=(int **)malloc(sizeof(int *)*(l));
		for (i = 0; i < l; i++){
			ld_match[i] = (int *) calloc(d,sizeof(int));
		}
		move(0,0);
		printf("K prechodu reky je treba %d pontonu.\n", res);
		free(border[0]);
		free(border[1]);
		free(border);
		for (i = 0; i < l; i++){
			free(ld_match[i]);
		}
		free(ld_match);
		t_c--;
	}
	return 0;
}