import java.util.*;


public class Most {

	/**
	 * @param args
	 */
	static Scanner sc=new Scanner(System.in);
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int pocet=sc.nextInt();
		int startX=0,startY=0,cilX=0,cilY=0;
		for (int i=1;i<=pocet;i++){
			int pocetKosticek=0;
			double prechod=1000000000;
			int rozmer=sc.nextInt();
			int[]od=new int[rozmer];
			int[]kam=new int[rozmer]; 
			//int []vzd=new int[rozmer];
			
			for (int j=0; j<rozmer;j++){
				od[j]=sc.nextInt();
				kam[j]=sc.nextInt();
			}
			
			for (int k=0;k<rozmer;k++){
				for (int l=0;l<rozmer;l++){
					if (prechod>(Math.sqrt((k-l)*(k-l)+(od[k]-kam[l])*(od[k]-kam[l])))){
						prechod=Math.sqrt((k-l)*(k-l)+(od[k]-kam[l])*(od[k]-kam[l]));
						startX=k+1;
						startY=od[k];
						cilX=l+1;
						cilY=kam[l]; //souradnice odkud vzjit 
					//	System.out.println(startX + " " + startY + " " +cilX+" "+ cilY);
						
					}
				}
				
			}
			
			 pocetKosticek=cilX-startX+cilY-startY;
			
			System.out.println("K prechodu reky je treba "+ pocetKosticek+" pontonu.");
		}
		
		
	}

}