THPT Chuyên Bến Tre

* Các bạn HS chú ý: Khi nộp bài máy chấm chỉ chấm test ví dụ của đề bài, sau khi kết thúc 
bài KT chúng tôi sẽ chấm lại với bộ test đầy đủ, vì vậy hãy test kỹ trước khi nộp bài mình.

Một số tổ chức tội phạm xuyên quốc gia sử dụng Internet để truyền tin cho nhau. Một trong các hình thức thường được dùng để che dấu nội dung của thông tin được truyền là dấu thông tin trong các bức tranh và gửi nó như gửi các ảnh thông thường. Cảnh sát quốc tế (interpol) vừa xác định được cách giám định một bức tranh của một nhóm tội phạm có chứa thông báo mật hay không. 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≤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'

                        BF    =  10111111

            6BF7F510F = 011010111111011111110101000100001111

Yêu cầu: 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ữu 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

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

Example

Input:
BF
6BF7F510F

Output:
2