import java.util.Scanner;
import java.util.regex.Pattern;
import java.util.regex.PatternSyntaxException;

public class Solution {

	public static void main( String[] args ) {
		
		Scanner sc = new Scanner( System.in );
		int testCases = Integer.parseInt( sc.nextLine() );
		
		while ( testCases > 0 ) {
			String pattern = sc.nextLine();

			try {
				Pattern.compile( pattern );
				System.out.println( "Valid" );
			}
			catch ( PatternSyntaxException pse ) {
				System.out.println( "Invalid" );
			}
			
			testCases--;
		}
		
		sc.close();
		
	}

}

Add day 28 solution