import java.util.Scanner;


public class Most {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int pocet = s.nextInt();
		for (int i = 0; i < pocet; i++) {
			int velikost = s.nextInt();
			int[] leve = new int[velikost];
			int[] prave = new int[velikost];
			
			for (int j = 0; j < velikost; j++) {
				int a = s.nextInt();
				int b = s.nextInt();
				leve[j] = a;
				prave[j] = b;
			}
			
			int a = -1; 
			int b = -1;
			int nejkratsi = Integer.MAX_VALUE;
			for (int j = 0; j < velikost; j++) {
				int hranice = prave[j] - leve[j];
				int spodni = Math.max(0, j-hranice);
				int horni = Math.min(velikost, j+hranice+1);
				for (int k = spodni; k < horni; k++) {
					int x1 = leve[j];
					int x2 = prave[k];
					int vzdalenost = (x1-x2)*(x1-x2) + (j-k)*(j-k);
					if (vzdalenost < nejkratsi) {
						nejkratsi = vzdalenost;
						a = j;
						b = k;
					}
				}
			}
			System.out.format("K prechodu reky je treba %d pontonu.\n", delkaMostu(leve[a], a, prave[b], b ));
		}
	}
	
	public static int delkaMostu(int x1, int y1, int x2, int y2) {
		int delka = Math.abs(x1-x2) + Math.abs(y1-y2);

		return delka;
	}
}