using System;

class Solution {
    static int max = 500;
    
    static bool[] Find(string re) {
        int k = 0;
        bool[] op = new bool[max + 1];
        op[0] = true;
        
        while (k < re.Length) {
            if (re[k] == '(') {
                k++;
                int p = k;
                int c = 1;
                bool[] sop = new bool[max + 1];
                
                while (c > 0) {
                    if (re[k] == '(') {
                        c++;
                    } else if ((c == 1) && ((re[k] == '|') || (re[k] == ')'))) {
                        bool[] r = Find(re.Substring(p, k - p));
                        p = k + 1;
                        
                        for (int i = 0; i <= max; i++) {
                            sop[i] = sop[i] || r[i];
                        }
                    }
                    
                    if (re[k] == ')') {
                        c--;
                    }
                    
                    k++;
                }
                
                if ((k < re.Length) && (re[k] == '*')) {
                    k++;
                    sop[0] = true;
                    
                    for (int i = max / 2; i > 0; i--) {
                        if (sop[i]) {
                            for (int j = i; j <= max; j += i) {
                                sop[j] = true;
                            }
                        }
                    }
                }
                
                for (int i = max; i >= 0; i--) {
                    bool rr = false;
                    
                    for (int j = 0; j <= i; j++)  {
                        rr = rr || op[i - j] && sop[j];
                    }
                    
                    op[i] = rr;
                }
            } else if ((k < re.Length - 1) && (re[k + 1] == '*')) {
                for (int i = 1; i <= max; i++) {
                    if (!op[i] && op[i - 1]) op[i] = true;
                }
                
                k += 2;
            } else if (re[k] == '*') {
                k++;
            } else {
                for (int i = max; i > 0; i--) {
                    op[i] = op[i - 1];
                }
                
                op[0] = false;
                k++;
            }
        }
        
        return op;
    }
    
    static void Main(String[] args) {
        int t = Int32.Parse(Console.ReadLine());
        
        for (int z = 0; z < t; z++) {
            int m = Int32.Parse(Console.ReadLine());
            bool[] op = Find("(" + Console.ReadLine() + ")");
            
            while ((m <= max) && !op[m]) m++;
            if (m > max) m = -1;
            
            Console.WriteLine(m);
        }
    }
}