import java.util.*;

class Most {

public static void main(String []args) {

	Scanner s = new Scanner(System.in);
	int c = s.nextInt();

	for (int i=0; i<c; i++) {
		int sz = s.nextInt();
		int [] left = new int[1000000];
		int [] right = new int[1000000];
		int lin = 0;
		int min = Integer.MAX_VALUE;
		for (int j=0; j<sz; j++) {
			left[lin] = s.nextInt();
			right[lin] = s.nextInt();
			
			for (int b=lin; lin - b < Math.min(min, Math.min(1000000, j)); b = (b + 1000000 - 1) % 1000000) {
				int a = (lin - b + 1000000) % 1000000;
				min = Math.min(min, Math.max(0, right[lin] - left[b]) + a);
				min = Math.min(min, Math.max(0, right[b] - left[lin]) + a);
			}

			lin = (lin + 1) % 1000000;
		}
		System.out.println("K prechodu reky je treba " + min + " pontonu.");
	}	

}


}