The world is stunned by the CodoVid virus, which is believed to be one of the deadliest viruses the world has ever seen. Due to its self-reproduction mechanism, the DNA sequence of the CodoVid virus grows at a high speed. The DNA sequence of CodoVid virus is a binary string consisting of 0’s and 1’s only. A codovid virus has an initial DNA sequence S1. Starting from day 2, each day codovid virus reproduces a new sequence and adds the new sequence to its DNA sequence.

The sequence of DNA added on the i^th day, S_i = Reverse(S_i-1) + Flip(S_i-1) + Reverse(S_i-1),

• The + symbol represents string concatenation operation.
• R() function returns the characters in reverse order. i.e. R(1100) = 0011
• F() function changes all the 0’s to 1’s and vice versa. i.e. F(1001) = 0110

So, on the first day the Codovid DNA sequence is S₁. On the second day the sequence is S₁+S₂. On the third day, the sequence will become S₁+S₂+S₃. So, it is an ever-growing sequence, S₁+S₂+S₃+ ...

An example will make it clear.

Let’s assume the Initial CodoVid DNA sequence on Day 1, S₁ = 100.

So, the first few characters of the CodoVid DNA sequence is: 100001011001100110100110100110100110100...

So, the 1^st character of the codovid DNA sequence is 1. Similarly, 2^nd, 3^rd, 4^th, 5^th is 0, 6^th character is 1 and 7^th character is 0 and so on.

In this problem, you are given the initial DNA sequence of the Codovid virus, S₁ and two integers L and R. You have to count the number of 1’s from the L^th character to the R^th character of the Codovid DNA sequence.

The input begins with an integer T (1 ≤ T ≤ 100) denoting the number of test cases. T test cases follow. Every case starts with a non-empty string S₁ (1 ≤ |S₁| ≤ 10⁴) in a single line. Next line of the input is an integer Q (1 ≤ Q ≤ 5000) denoting the number of queries. Then follow Q lines containing two integers L, R (1 ≤ L ≤ R ≤ 10¹⁷). You may safely assume that, Sum of length(S1) over all test cases ≤ 5 x 10⁵.

For each test case, Print the case number in the format Case X: in a single line , where X is the case number. Then, for each query of that test case, print the desired answer in a single line.

Please check the samples for further clarification.