// Arup Guha
// 11/17/2011
// Solution to Fall 2011 COT 4210 Program #2

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

public class SAT_to_VC {

	public static void main(String[] args) throws Exception {
	
		// Reads in multiple problem instances from 3sat.txt.
		Scanner fin = new Scanner(new File("3sat.txt"));
		PrintWriter fout = new PrintWriter(new File("vc.txt"));
		
		int numProblems = fin.nextInt();
		fout.write(numProblems+"\n");
		
		// Go through each one.
		for (int i=0; i<numProblems; i++) {
		
			// Create this SAT instance.
			sat thisProblem = new sat(fin);
		
			// Reduces it to an instance of vertex cover and outputs that instance.
			graphk thisVC = thisProblem.reduceToVC();
			fout.write(thisVC.toString());
		}
		
		fin.close();
		fout.close();
	}
}