import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Pattern;

public class Most {

	public static void main(String[] args) throws IOException {
		BufferedReader buf = new BufferedReader(
				new InputStreamReader(System.in));
		String line = buf.readLine();
		Pattern pattern = Pattern.compile("\\s");

		int n = Integer.parseInt(line);

		for (int i = 0; i < n; i++) {
			line = buf.readLine();
			int height = Integer.parseInt(line);

			int[] l = new int[height];
			int[] r = new int[height];

			for (int j = 0; j < height; j++) {
				line = buf.readLine();
				String[] split = pattern.split(line);
				l[j] = Integer.parseInt(split[0]);
				r[j] = Integer.parseInt(split[1]);
			}

			int min = Integer.MAX_VALUE;

			int lIdx = 0;
			int rIdx = 0;
			while (lIdx < height && rIdx < height) {
//				System.out.println(lIdx + " " + rIdx);

				int dist = r[rIdx] - l[lIdx]  + Math.abs(rIdx-lIdx);
				min = Math.min(min, dist);
				int distL = Integer.MAX_VALUE;
				int distR = Integer.MAX_VALUE;
				
				if (lIdx + 1 < height) {
//					System.out.println("pom: " + l[lIdx] + " " + r[rIdx]);
					distL = r[rIdx] - l[lIdx + 1] + Math.abs((lIdx+1) - rIdx);
				}
				if (rIdx + 1 < height) {
					distR = r[rIdx + 1] - l[lIdx] + Math.abs(lIdx - (rIdx+1));
				}
				if (distL < distR) {
					lIdx++;
					min = Math.min(min, distL);
				} else {
					rIdx++;
					min = Math.min(min, distR);
				}
//				System.out.println(min);
			}

			if (lIdx == height - 1) {
				while (rIdx+1 < height) {
					int distR = r[rIdx + 1] - l[lIdx] + Math.abs(lIdx - (rIdx+1));
					rIdx++;
					min = Math.min(min, distR);
				}
			}

			if (rIdx == height - 1) {
				while (lIdx+1 < height) {
					int distL = r[rIdx] - l[lIdx + 1] + Math.abs((lIdx+1) - rIdx);
					lIdx++;
					min = Math.min(min, distL);
				}
			}

			System.out.println("K prechodu reky je treba " + min + " pontonu.");
		}

	}

}