hackercupai/hackercup huggingface dataset:
**Note: This is the easier version of [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2/problems/A2). This version involves a string, but chapter 2 involves an array of integers that can change with updates.**

A string is *perfectly balanced* if its length is even, and the first half of the string can be shuffled to make the string a palindrome. For example, "`abab`" and "`dood`" are perfectly balanced, but "`racecar`" and "`doodad`" are not.

A string is *almost perfectly balanced* if you can delete exactly one character from it to make it perfectly balanced. Some examples are "`classical`", "`intelligent`", and "`www`".

{{PHOTO_ID:1262846811180772|WIDTH:700}}

You are given a larger template string \(S\), and \(Q\) substrings, the \(i\)th of which is \(S_{L_i..R_i}\). For how many of these \(Q\) queries is the substring almost perfectly balanced?

# Constraints

\(1 \le T \le 90\)
\(1 \le |S| \le 10^6\)
\(S_i \in\) {'`a`', ..., '`z`'}
\(1 \le Q \le 10^6\)
\(1 \le L_i \le R_i \le |S|\)

The sum of \(|S|\) across all test cases is at most \(4{,}000{,}000\).
The sum of \(Q\) across all test cases is at most \(4{,}000{,}000\).

# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing a single template string \(S\). Then, there is a line containing a single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which contains two space-separated integers \(L_i\) and \(R_i\).

# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "`, followed by a single integer: the number of queries which are an almost perfectly balanced substring.

# Sample Explanation

In the first case, the template string is "`singingbanana`".

For the first query, the substring is "`banan`". You can delete the `"b"` to get "`anan`" then reorder the first half of the string to get `"naan"`, which is a palindrome. Thus, "`banan`" is an almost perfectly balanced substring.

For the second query, the substring is "`anana`". You can delete the second "`a`" to get "`anna`", which is a palindrome. Thus, "`anana`" is an almost perfectly balanced substring.

For the third query, the substring is "`ban`". You cannot delete any character to get an almost perfectly balanced substring.

For the fourth query, the substring is "`nan`". You can delete the "`a`" to get "`nn`", which is a palindrome. Thus, "`nan`" is an almost perfectly balanced substring.

For "`singing`", you can create "`gniing`".

In the second test case, the first, second, and third queries are almost perfectly balanced substrings, but the fourth is not.

In the third test case, the first, second, third, and fourth queries are almost perfectly balanced substrings, but the fifth and sixth are not.