namespace _2.ValidBrackets
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            List<string> results = new List<string>();
            for (int i = 0; i < n; i++)
            {
                string brackets = Console.ReadLine();
                bool isValid = AreBracketsValid(brackets);
                if (isValid)
                {
                    results.Add("valid");
                }
                else
                {
                    results.Add("invalid");
                }
            }
            Console.WriteLine(String.Join(Environment.NewLine, results));
        }

        private static bool AreBracketsValid(string brackets)
        {
            Stack<char> opening = new Stack<char>();
            for (int i = 0; i < brackets.Length; i++)
            {
                if (brackets[i]=='(')
                {
                    opening.Push(brackets[i]);
                }
                else if (brackets[i]==')')
                {
                    if (opening.Count==0||opening.Pop()!='(')
                    {
                        return false;
                    }
                }
                else if (brackets[i] == '*')
                {
                    bool open = AreBracketsValid(brackets.Substring(0, i) + ")" + brackets.Substring(i + 1));
                    bool close = AreBracketsValid(brackets.Substring(0, i) + "(" + brackets.Substring(i + 1));
                    bool none = AreBracketsValid(brackets.Substring(0, i) + brackets.Substring(i + 1));
                    if (open==true||close==true||none==true)
                    {
                        return true;
                    }
                    return false;
                }
            }
            if (opening.Count!=0)
            {
                return false;
            }
            return true;
        }
    }
}