Bạn Trung rất thích con số và lý thuyết mật mã, hiện nay đang có một xu thế là mã hóa dữ liệu qua các bức tranh, người bình thường khó phát hiện ra bức trang có chứa thông tin mật. Ví dụ một cách mã hóa như sau: Bức tranh chứa thông báo mật nếu như xâu bit biểu diễn nó chứa chữ ký ~S~ là một xâu gồm ~4*N~ bit cho trước ~(0 < N \le 250)~. Để giải mã thông báo mật được che dấu cần xác định số lần xuất hiện chữ ký trong tranh. Các đoạn xâu bit chứa chữ ký trong tranh có thể giao nhau. Tranh được biểu diễn dưới dạng dãy chữ số trong hệ đếm cơ số ~16~. Chữ ký ~S~ được ghi nhận dưới dạng dãy gồm ~N~ chữ số của hệ đếm cơ số ~16~. Ví dụ: chữ ký BF xuất hiện 2 lần trong bức tranh 6BF7F510F, thực vậy ta có ~BF = 10111111, 6BF7F510F = 0110\underline{1011111101111111}0101000100001111~ (đoạn gạch chân ~BF~ xuất hiện ~2~ lần).

Bài toán hôm nay do bạn Trung đưa ra cho các bạn là: Cho chữ ký ~S~ và tranh. Hãy xác định số lần xuất hiện chữ ký này trong tranh.

Input

Dòng đầu tiên chứa xâu chữ ký ~S~.

Dòng thứ hai chứa thông tin về bức tranh dưới dạng dãy gồm không quá ~40000~ chữ số của hệ đếm cơ số ~16~.

Output

In ra một số nguyên là số lần xuất hiện chữ ký trong tranh.

Samples

Sample Input 1

BF
6BF7F510F

Sample Output 1

2