On considère l’alphabet A = {a, b} et on donne la définition inductive d’un regex R comme

1. R est une lettre de l’alphabet A
2. R est (P.S) où P et S sont deux regex
3. R est (P|S) où P et S sont deux regex
4. R est (P*) où P est un regex
5. R est (P+) où P est un regex

Toute expression régulière sera nécessairement parenthésée. On définit alors l’ensemble L(R) des mots reconnus par un regex R :

1. R est “(x)” où x est dans l’alphabet A; L(R) = {x}
2. R est (P.S); L(R) = {ps, p ∈ L(P) ∧ s ∈ L(S)}
3. R est (P|S); L(R) = L(P) ∪ L(S)
4. R est (P*); L(R) = La concaténation de 0 ou plusieurs mots reconnus par P
5. R est (P+); L(R) = La concaténation d’un ou plusieurs mots reconnus par P

Input

2N lignes de regex R et de nombres n.

• 150 ≤ N ≤ 300
• 2 ≤ n ≤ 16
• Profondeur p(R) du regex : 2 ≤ p(R) ≤ 5

Output

Il est demandé d’afficher N lignes, contenant chacune le nombre de mots de longeurs au plus n dans l’alphabet A* reconnus par le regex.

Exemples

Input :

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

Output :

16
4410
15