Cho hai xâu x,y. Xét dãy vô hạn các xâu ~f_1,f_2,…~ trong đó:

$$\begin{cases} f_i=\ 'A',\ nếu\ i=1 \\ f_i=\ 'B',\ nếu\ i=2 \\ f_i =f_{i-1}+f_{i-2},\ nếu\ i>2 \end{cases}$$

Ví dụ dãy các xâu f_{1…8} là:
F1 = A
F2 = B
F3 = BA
F4 = BAB
F5 = BABBA
F6 = BABBABAB
F7 = BABBABABBABBA
F8 = BABBABABBABBABABBABAB

Yêu cầu:

Cho xâu ~S~, hãy xác định số lần xuất hiện xâu ~S~ trong xâu ~f_n~. Chú ý: hai lần xuất hiện của trong ~f_n~ không nhất thiết phải là các xâu rời nhau hoàn toàn.

Dữ liệu:

Gồm không quá 10 dòng, mỗi dòng ghi xâu ~s~ (độ dài không quá 1000) và số nguyên dương ~n≤90~ cách nhau ít nhất một dấu cách.

Kết quả:

Mỗi dòng kết quả ra ứng với một bộ dữ liệu trên một dòng của dữ liệu

Input

A 3
AB 3
BABBAB 8

Output

1
0
4