// Dan Deblasio 7/22/08
import java.io.*;
import java.util.*;

public class mathematician{

	// Being lazy, only one stack is needed.
	public static boolean stack[] = new boolean[10];
	public static int index = 0;	

	public static void main(String[] args)throws FileNotFoundException{
		Scanner fin = new Scanner(new File("mathematician.in"));

		int n = Integer.parseInt(fin.nextLine());
		
		// Go through cases.
		for(int caseNum = 1;caseNum<=n;caseNum++){
			index = 0;
			String print = "";
			boolean tooDeep = true;
			boolean valid = true;
			char[] line = fin.nextLine().toCharArray();
			
			// Go through the line, only paying attention to ( and ).
			for(int i=0;i<line.length;i++){
				if(line[i]=='('){
					tooDeep &= push();
					print += index + " ";
				}else if(line[i]==')'){
					print += index + " ";
					valid &= pop();
				}
			}
			
			// Output based on what happened with the stack.
			if(!tooDeep){
				System.out.println("Case #"+caseNum+": Too Deep!!");
			}
			else if(valid && index==0){
				System.out.println("Case #"+caseNum+": Valid");
				System.out.println("        "+ print);
			}else{
				System.out.println("Case #"+caseNum+": Not Valid");
			}
		}
	}

	// Push an item onto the stack.
	public static boolean push(){
		if(index>=10) return false;
		stack[index++] = true;
		return true;
	}

	// Pop an item off the stack.
	public static boolean pop(){
		if(index<=0) return false;
		stack[--index] = false;
		return true;
	}

}