import java.util.*;

class Most {

public static int brutalize(int i) {
	return (i + 1000011) % 1000011;
}

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[1000011];
		int [] right = new int[1000011];
		int lin = 0;
		int min = Integer.MAX_VALUE;
		for (int j=0; j<sz; j++) {
			left[lin] = s.nextInt();
			right[lin] = s.nextInt() + 1;
			
			for (int b=lin; brutalize(lin - b) <= Math.min(min, Math.min(1000011, j)); b = brutalize(b - 1)) {
				int a = brutalize(lin - b);
				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 = brutalize(lin + 1);
		}
		System.out.println("K prechodu reky je treba " + (min-1) + " pontonu.");
	}	

}


}