We condiser the alphabet *A* = {a, b} and we give the inductive definition of a regex R as follows.

- R is a letter of the alphabet
*A* - R is (P.S) where P and S are two regex
- R is (P|S) where P and S are two regex
- R est (P*) where P is a regex
- R is (P*) where P is a regex

Every regular expression will *necessarily* parenthesized. We then define the set *L*(R) of the words recongnized by a regex R:

- R is “(x)” where x is in the alphabet
*A*;*L*(R)= {x} - R is (P.S);
*L*(R) = {ps, p ∈*L*(P) ∧ s ∈*L*(S)} - R is (P|S);
*L*(R) =*L*(P) ∪*L*(S) - R is (P*);
*L*(R) = The concatenation of 0 or many words recognized by P - R is (P+);
*L*(R) = The concatenation of one or many words recognized by P

## Input

*2N* lines of regex *R* and numbers *n*.

- 150 ≤
*N*≤ 300 - 2 ≤
*n*≤ 16 - Depth
*p*(R) du regex : 2 ≤*p*(R) ≤ 5

## Output

It’s required to display *N* lines, containing each the number of words of maximal length *n* in the alphabet *A** recognized by the regex.

# Examples

**Input :**

```
(a.((((b+)|(b|b))|b)*))
16
(((((b+).(a.a))+)|a)*)
15
(b*)
14
```

**Output :**

```
16
4410
15
```