সম্ভবত , তোমরা সবায় জাপানিজ জনপ্রিয় কার্টুন চরিত্র নবিতা আর সিজুকা কে চেন।নবিতা এবং সিজুকা খুব ভালো বন্ধু।
যাইহোক , সিজুকা একটা বিষেশ ধরনের স্ট্রিং পছন্দ করে যার নাম Tokushuna
একটি স্ট্রিং Tokushuna হবে যদি
এখানে |T| =স্ট্রিং টার দৈর্ঘ্য ,উদাহারন 10001 ,101,10001 এগুলা Tokushuna স্ট্রিং কিন্তু 1100 ,1111, 0000 এগুলা Tokushuna স্ট্রিং নয়।
একদিন সিজুকা নবিতা কে একটা সমস্যা দিলো এবং সেটা সলভ করতে পারলে ডেটে যাওয়ার অফার দিলো ।
সিজুকা নবিতাকে একটা স্ট্রিং S দিয়ে বলল S এর কতগুলা সাবস্ট্রিং Tokushuna স্ট্রিং হবে।
নবিতা ডেটে যেতে চায় কিন্তু তোমরা জানো সে গনিত এবং গননায় দূর্বল এবং তখন তার কাছে ডরিমন ও ছিলনা সাহায্য করার জন্য ।
তাই নবিতার তোমার সাহায্য প্রযোজন।
প্রথম লাইনে একটা পূর্ন্যসংখ্যা T দেওয়া থাকবে যেটা হলো টেস্ট কেস এর সংখ্যা ।
এর প্রতি টেস্ট কেস এ একটা বাইনারি স্ট্রিং S দেওয়া থাকবে যেটা শুধু 0 এবং 1 দিয়েই গঠিত হবে।
সাবটাস্ক #1 (50 points)
1 ≤ T ≤ 100
1 ≤ |S| ≤ 100
সাবটাস্ক #2 (50 points)
1 ≤ T ≤ 100
1 ≤ |S| ≤ 105
প্রতি টেস্ট কেস এ এক লাইনে প্রিন্ট করো Case X: Y যেখানে X হলো টেস্ট কেস এর নাম্বার এবং Y হলো S এর সবগুলা সাবস্ট্রিং এর ভেতর Tokushuna স্ট্রিং এর সংখ্যা।
Input | Output |
---|---|
3 10001 10101 1001001001 | Case 1: 1 Case 2: 2 Case 3: 3 |
In the first case |
লক্ষ করো , প্রথম টেস্ট কেস এ 10001 এটা পুরোটায় এটা Tokushuna স্ট্রিং । এবং মোট ১ টার বেশি Tokushuna স্ট্রিং নেই ।
দ্বিতীয় কেসে , সাবস্ট্রিং S[1-3] = 101 এবং S[3-6] 101 হলো Tokushun স্ট্রিং ।