import java.io.*; import java.util.*; public class Solution { static final int LIM = 500; static BitSet charToLen(char ch, List<BitSet> evalres) { return (ch > 999) ? evalres.get(ch-1000) : constLen(1); } static BitSet constLen(int len) { BitSet result = new BitSet(len+1); if (len <= LIM) result.set(len); return result; } static BitSet applyStar(BitSet set) { BitSet result = new BitSet(LIM+1); result.set(0); for (int i = result.nextSetBit(0); 0 <= i && i <= LIM; i = result.nextSetBit(i+1)) { for (int j = set.nextSetBit(0); 0 <= j && i+j <= LIM; j = set.nextSetBit(j+1)) { result.set(i+j); } } return result; } static BitSet concat(BitSet s1, BitSet s2) { BitSet result = new BitSet(); for (int i = s1.nextSetBit(0); 0 <= i && i <= LIM; i = s1.nextSetBit(i+1)) for (int j = s2.nextSetBit(0); 0 <= j && i+j <= LIM; j = s2.nextSetBit(j+1)) result.set(i+j); return result; } static BitSet reglen(String regex, List<BitSet> evalres) { // - brackets while (regex.indexOf('(') >= 0) { int si = regex.indexOf('('); int ei; int open = 1; for (ei = si+1; open > 0; ei++) { if (regex.charAt(ei) == '(') open++; if (regex.charAt(ei) == ')') open--; } evalres.add(reglen(regex.substring(si+1, ei-1))); regex = regex.substring(0, si) + (char)(evalres.size() + 999) + regex.substring(ei, regex.length()); } BitSet result = new BitSet(LIM+1); // - edge cases if (regex.length() == 0) { result.set(0); return result; } // - kleene star for (int i = regex.indexOf('*'); i >= 0; i = regex.indexOf('*')) { evalres.add(applyStar(charToLen(regex.charAt(i-1), evalres))); regex = regex.substring(0, i-1) + (char)(evalres.size() + 999) + regex.substring(i+1, regex.length()); } // - concatenation and alternation StringTokenizer tokenizer = new StringTokenizer(regex, "|"); while(tokenizer.hasMoreTokens()) { String p = tokenizer.nextToken(); BitSet set = new BitSet(LIM+1); set.set(0); for (int i = 0; i < p.length(); i++) set = concat(set, charToLen(p.charAt(i), evalres)); result.or(set); } return result; } static BitSet reglen(String regex) { return reglen(regex, new ArrayList<BitSet>()); } public static void main(String[] args) { Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in), 256 << 10)); int testsNumber = in.nextInt(); for (int test = 0; test < testsNumber; test++) { int minlen = in.nextInt(); System.out.println(reglen(in.next()).nextSetBit(minlen)); } in.close(); } }