Cho dãy chuỗi Fibonacci được định nghĩa như sau:

• F(0) = "0"
• F(1) = "1"
• F(n) = F(n - 1) + F(n - 2)

Trong đó, phép "+" đại diện cho phép nối chuỗi.

Nhiệm vụ: Với mỗi test case, cho trước một số nguyên n (\( 0 \leq n \leq 100\) ) và một mẫu chuỗi con p không rỗng có độ dài tối đa 100.000 ký tự. Hãy đếm xem chuỗi con ppp xuất hiện bao nhiêu lần trong chuỗi Fibonacci F(n). Các lần xuất hiện có thể giao nhau.

Đầu vào:

• Dòng đầu tiên chứa số nguyên n.

• Dòng thứ hai chứa chuỗi mẫu p.

Đầu ra:

• Với mỗi test case, hiển thị kết quả dưới dạng "Case #x: y", trong đó x là số thứ tự của test case, và y là số lần chuỗi con p xuất hiện trong F(n)

Ví dụ:

Input:

6
10

Ouput:

Case #1: 5