== include(page="template/taskheader" task_id="bytes") ==

Seeking treasures of immense value to add to his almighty random knapsack, Prosto is travelling around the world. During one of his journeys he found a room filled with chests, each being locked. On every chest there is a boolean formula engraved on it.
 
The boolean formulas are XOR sums of multiple clauses, where a clause is the AND sum of some literals, which can be negated.
 
Alongside the formula on the chest, there is engraved a number $k$, which represents the number of distinct literals which can appear in the given formula. The $i$-th literal is represented as the $i$-th lowercase letter of the english alphabet e.g. the first literal is 'a', the second literal is 'b' and so on.
 
In order to unlock a chest you need to find the number of ways to assign each literal $0$ or $1$ such that the given formula evaluates to $1$.
 
Let's say we have a chest with $k=3$ variables and the following formula: (a AND b) XOR (b AND c) XOR (a AND c). If the tuple of literals $(a,b,c)$ is equal to one of the following tuples: $(1,1,0)$, $(1,0,1)$, $(0,1,1)$, $(1,1,1)$ then the given expression is $1$, so the answer is $4$.
 
Our protagonist promises you glory and $100$ points if you can help him find the keys to some of his chests.

Poveste şi cerinţă...

h2. Date de intrare

The first line of the file $bytes.in$ contains $T$, the number of chests.
 
For each chest you are given a number $k$ representing the number of literals, and a string $s$ which represents the formula written on the chest.

Fişierul de intrare $bytes.in$ ...

h2. Date de ieşire

The output file $bytes.out$ will contain on $T$ lines the keys of the chests in the order they appear in the input.

În fişierul de ieşire $bytes.out$ ...

h2. Restricţii

* $1 ≤ T ≤ 15$
* $1 ≤ k ≤ 14$
* $1 ≤ |s| ≤ 10^5$
* For tests worth $20$ points, $1 ≤ k ≤ 10$
* For tests worth $30$ more points, there aren't any negated literals
* For tests worth another $20$ points, $1 ≤ k ≤ 12$
* The scores from the contest might be different than the scores you get here

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. bytes.in |_. bytes.out |

| 3
4
@(c&d)^(!a&b&!c)^(b)@
4
@(!c)@
4
@(!c&!d)^(!a&c&!d)^(a&!b&c)@
| 6
8
8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie