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