import java.util.Scanner;
public class Main{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
int a,d,e,f,g,h,i,j,k,l,m,n;
int N = input.nextInt();
String s = input.nextLine();
for(a=0; a<N; a++)
{
s = input.nextLine();
d = s.length();
f = 0;
for(e=1 ; e<(d+1)/2 ; e++)
{
g = (s.charAt(d-2*e)-48) * 2;
if( (s.charAt(d-2*e)-48) * 2 >= 10 )
{
g = (s.charAt(d-2*e)-48) * 2;
h = g%10;
g = g -10;
g = h + 1;
}
else
g = (s.charAt(d-2*e)-48) * 2;
f += g;
}
k = 0;
for(i=1 ; i<(d+1)/2; i++)
{
j = s.charAt(d-(2*i -1)) - 48;
k += j;
}
l=0;
m=0;
n=0;
if(13 > d && d > 16)
l = 1;
else if(s.charAt(0)==4 || s.charAt(0) == 5 || s.charAt(0)==6)
m = 0;
else if(s.charAt(0)==3)
{
if(s.charAt(1)==7)
n = 0;
else
n = 1;
}
else m =1;
if( (f + k) % 10 == 0 && m ==0 && n == 0)
System.out.println("Valid");
else if( l==1 || n==1 || m ==1 )
System.out.println("Invalid");
}
}
}