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); } } }