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

#define MAXK 12000000

int a[MAXK];
int b[MAXK];

int Min(int a, int b)
{
	return (a < b) ? a : b;
}

int Max(int a, int b)
{
	return (a > b) ? a : b;
}

void Adjust(int i, int j)
{
	a[i] = Max(a[i], a[j] - 1);
	b[i] = Min(b[i], b[j] + 1);
}

int main()
{
	int n;
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++)
	{
		int k;
		scanf("%d", &k);
		
		for(int i = 0; i < k; i++)
		{
			scanf("%d%d", a + i, b + i);
		}
		
		for(int i = 0; i < k - 1; i++)
		{
			Adjust(i, i + 1);
			Adjust(i + 1, i);
		}
		
		for(int i = k - 2; i >= 0; i--)
		{
			Adjust(i, i + 1);
			Adjust(i + 1, i);
		}
		
		int min = 1 << 30;
		for(int i = 0; i < k; i++)
		{
			if(b[i] - a[i] < min)
			{
				min = b[i] - a[i];
			}
		}
		
		printf("K prechodu reky je treba %d pontonu.\n", min);
	}
	
	return 0;
}