You must know about Gauss, the famous mathematician. Back in late 1700s, he was at

elementary school. Gauss was asked to find the sum of the numbers from 1 to 100.

The question was assigned as busy work by the teacher. He amazed his teacher

with how quickly he found the sum of the integers from 1 to 100 to be 5050. Gauss

recognized he had fifty pairs of numbers when he added the first and last number in

the series, the second and second-last number in the series, and so on. For example:

(1 + 100), (2 + 99), (3 + 98), ..., (50 + 51). Each pair has a sum of 101 and there

are 50 pairs.

History repeats itself. Jojos teacher assign a busy work to the students. The teacher

believes that there will be no shortcut to finish this task in a minute. The teacher gives

N integers A1, A2, ..., AN to the students. The teacher also gives Q questions. Each

question contains two integers L and R asking the sum of all Ai where L <= Ai <= R.

As a good friend of Jojo, help Jojo to amaze his teacher. Answer all the questions!

Format Input

There are T testcases. Every testcase consists of a line with an integers N followed by a

line consists of N integers A1, A2, ..., AN as described above. Followed by a line consists

of an integers Q and Q lines which each consists of two integers L and R as described

above.

Format Output

Output T testcases with format Case #X:, where X indicates the testcase number

and then followed by Q lines which each consists of an integers indicates the answer of

each question.

Constraints

1 T 3

1 N, Q 30000

1 Ai

, L, R 10^9

Sample Input (standard input)

3

6

3 2 1 3 5 1

3

3 3

2 3

1 5

5

4 5 6 7 8

7

4 4

4 5

4 6

4 7

4 8

4 9

3 8

5

11 12 13 14 15

3

1 10

16 20

1 20

Sample Output (standard output)

Case #1:

6

8

15

Case #2:

4

9

15

22

30

30

30

Case #3:

0

0

65

Note : Use C Language , Dont Use Stdlib as you can use stdio.h math.h string.h only