#include<iostream>
#include<map>
#include<string>
#include <vector>
using namespace std;

map<char, int> word;

int main()
{

	string s;
	cin >> s;
	while(s != "0")
	{
		char m;
		for (int i = 0; i < 26; ++i)
		{
			word['A' + i] = 0;    
		}
		for(int i = 0; i < s.size(); i++)
		{
			word[s[i]]++;
			if(i == 4)
				m = s[i];
		}

		int num;
		cin >> num;
		for(int i = 0; i < num; i++)
		{
			cin >> s;
			if(s.size() > 9 || s.size() < 4)
			{
				cout << s << " is invalid" << endl;
				continue;
			}
			bool mid = false;
			for(int j = 0; j < s.size(); j++)
			{
				if(s[j] == m)
				{
					mid = true;
					break;
				}
			}
			if(!mid)
			{
				cout << s << " is invalid" << endl;
				continue;
			}

			map<char, int> temp = word;
			for(int j = 0; j < s.size(); j++)
			{
				if(temp[s[j]] > 0)
					temp[s[j]]--;
				else
				{
					mid = false;
					break;
				}
			}
			if(mid)
			{
				cout << s << " is valid" << endl;
			}

			else
			{
				cout << s << " is invalid" << endl;
			}
		}
		cin >> s;
	}
}