Limits 1s, 512 MB

সম্ভবত , তোমরা সবায় জাপানিজ জনপ্রিয় কার্টুন চরিত্র নবিতা আর সিজুকা কে চেন।নবিতা এবং সিজুকা খুব ভালো বন্ধু।
যাইহোক , সিজুকা একটা বিষেশ ধরনের স্ট্রিং পছন্দ করে যার নাম Tokushuna

একটি স্ট্রিং Tokushuna হবে যদি

  • এটির দৈর্ঘ্য ৩ এর সমান অথবা ৩ এর চেয়ে বড় হবে (|T| ≥ 3)
  • এটির প্রথম এবং শেষ অক্ষর '1' (এক) হবে
  • এটাতে (|T|-2) সংখ্যক '0' (শুন্য) থাকবে

এখানে |T| =স্ট্রিং টার দৈর্ঘ্য ,উদাহারন 10001 ,101,10001 এগুলা Tokushuna স্ট্রিং কিন্তু 1100 ,1111, 0000 এগুলা Tokushuna স্ট্রিং নয়।

একদিন সিজুকা নবিতা কে একটা সমস্যা দিলো এবং সেটা সলভ করতে পারলে ডেটে যাওয়ার অফার দিলো ।
সিজুকা নবিতাকে একটা স্ট্রিং S দিয়ে বলল S এর কতগুলা সাবস্ট্রিং Tokushuna স্ট্রিং হবে। নবিতা ডেটে যেতে চায় কিন্তু তোমরা জানো সে গনিত এবং গননায় দূর্বল এবং তখন তার কাছে ডরিমন ও ছিলনা সাহায্য করার জন্য ।
তাই নবিতার তোমার সাহায্য প্রযোজন।

Input

প্রথম লাইনে একটা পূর্ন্যসংখ্যা T দেওয়া থাকবে যেটা হলো টেস্ট কেস এর সংখ্যা ।
এর প্রতি টেস্ট কেস এ একটা বাইনারি স্ট্রিং S দেওয়া থাকবে যেটা শুধু 0 এবং 1 দিয়েই গঠিত হবে।

সাবটাস্ক

সাবটাস্ক #1 (50 points)
1 ≤ T ≤ 100
1 ≤ |S| ≤ 100

সাবটাস্ক #2 (50 points)
1 ≤ T ≤ 100
1 ≤ |S| ≤ 105

Output

প্রতি টেস্ট কেস এ এক লাইনে প্রিন্ট করো Case X: Y যেখানে X হলো টেস্ট কেস এর নাম্বার এবং Y হলো S এর সবগুলা সাবস্ট্রিং এর ভেতর Tokushuna স্ট্রিং এর সংখ্যা।

Sample

InputOutput
3
10001
10101
1001001001
Case 1: 1
Case 2: 2
Case 3: 3

In the first case $\texttt{10001}$ is itself is a Tokushuna string. In the second case there are 2 substrings (S[1:3] 101 and S[3:6]) that are $\texttt{101}$ that are Tokushuna string.


লক্ষ করো , প্রথম টেস্ট কেস এ 10001 এটা পুরোটায় এটা Tokushuna স্ট্রিং । এবং মোট ১ টার বেশি Tokushuna স্ট্রিং নেই ।
দ্বিতীয় কেসে , সাবস্ট্রিং S[1-3] = 101 এবং S[3-6] 101 হলো Tokushun স্ট্রিং ।

Submit

Login to submit.

Statistics

80% Solution Ratio
prodip_bsmrstuEarliest, Aug '20
iammarajulFastest, 0.0s
Aimon026Lightest, 0 B
zahid147Shortest, 95B
Toph uses cookies. By continuing you agree to our Cookie Policy.