import java.util.*; 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 N = Integer.parseInt(sc.nextLine());

     for(int i=0;i<N;i++){
        String pattern = sc.nextLine();
        try {
            Pattern.compile(pattern); // Attempt to compile the pattern
            System.out.println("Valid");
        } catch (PatternSyntaxException e) {
            System.out.println("Invalid");
        }
    }
  }  
}