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

1. R is a letter of the alphabet A
2. R is (P.S) where P and S are two regex
3. R is (P|S) where P and S are two regex
4. R est (P*) where P is a regex
5. 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:

1. R is “(x)” where x is in the alphabet A; L(R)= {x}
2. R is (P.S); L(R) = {ps, p ∈ L(P) ∧ s ∈ L(S)}
3. R is (P|S); L(R) = L(P) ∪ L(S)
4. R is (P*); L(R) = The concatenation of 0 or many words recognized by P
5. 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