import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class B {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		String line = bfr.readLine();
		String[] lineSplit;
		int n = Integer.parseInt(line);
		
		int [][] p = new int[1000001][2];
		
		for(int i = 0;i<n;i++)
		{
			
			
			int min = Integer.MAX_VALUE;
			
			int k = Integer.parseInt(bfr.readLine());
			
			for(int j = 0;j<k;j++){
				line = bfr.readLine();
				lineSplit = line.split(" ");
				
				int xA2 = p[j][0] = Integer.parseInt(lineSplit[0]);
				int xB2 = p[j][1] = Integer.parseInt(lineSplit[1]);
				
				
				
				// doleva nahoru
				
				for (int o = 0; o < min; o++){
					if (j-o < 0){
						break;
					}
					
					int xA1 = p[j - o][0];
					//int y1 = p[j - o][1];
					
					int mR = m(xA1, o, xB2, 0);
					
					if (mR < min){
						min = mR;
					}
				}
				
				// doprava nahoru
				
				for (int o = 0; o < min; o++){
					if (j-o < 0){
						break;
					}
					
					//int xA1 = p[j - o][0];
					int xB1 = p[j - o][1];
					
					int mR = m(xB1, o, xA2, 0);
					
					if (mR < min){
						min = mR;
					}
				}
				
				
				
			}
			System.out.println("K prechodu reky je treba "+ min + " pontonu.");
		}

	}

	public static int m(int x1, int y1, int x2, int y2){
		return (Math.abs(x2 - x1) + Math.abs(y2-y1));
	}
	
}