import java.util.Scanner;
import java.io.*;

/*
 * Lab 8
 *
 * Author: Robin Dawes
 *
 * Date: 20081111
 *
 * Comment: 
 *
 */

public class Greed {

    static int instances;
    static int numOfSups;
    static SupervisorHeap S;
    
    
 
    public static void main (String[] argv) throws Exception {
        Scanner myScanner = new Scanner(new File("Lab_8_Data.txt"));
        // find out how many instances
        instances = myScanner.nextInt();
        for (int i = 0; i < instances; i++) {
            System.out.println("\nInstance " + i + " input: ");
            numOfSups = myScanner.nextInt();
            S = new SupervisorHeap();
            
            for (int d = 0; d < numOfSups; d++){
                Supervisor temp = new Supervisor(myScanner.nextInt(),myScanner.nextInt());
                temp.showTimes();
                S.insert(temp, 1);
            } 
            
            System.out.println("Sorted : ");
            int timeToWalk = -1;
            int[] solution = new int[numOfSups];
            int countTimes = 0;
            // this loop prints the supervisors' times in sorted order, and also computes the solution
            for (int c = 0; c < numOfSups; c++) {
                Supervisor next = S.extractMin(1);
                next.showTimes();
                if (next.getVal(0) > timeToWalk) {
                    timeToWalk = next.getVal(1);
                    solution[countTimes] = timeToWalk;
                    countTimes++;
                    
                }
            }
            System.out.print("Solution : ");
            for (int d = 0; d < countTimes; d++) System.out.format("%10d",solution[d]);
            System.out.println();
    
            
        }              
    } // main
    
} // Greed class