// Arup Guha
// 7/25/2011
// Example for COT 4210 written in class.
// Edited on 11/17/2011 and broken into separate files to allow for easier reuse.

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

public class SAT_to_CLIQUE {

	public static void main(String[] args) throws Exception {
	
		// Reads in a file with a file format that allows for multiple input instances of 3-sat.
		Scanner fin = new Scanner(new File("3sat.txt"));
		
		int numProblems = fin.nextInt();
		
		// Go through each problem instance.
		for (int i=0; i<numProblems; i++) {
		
			sat thisProblem = new sat(fin);
		
			// Reduces it to an instance of clique and outputs that instance.
			graphk thisClique = thisProblem.reduceToClique();
			System.out.println(thisClique);
		}
	}
}