BOXSCHOC - Boxes of Chocolate

Choco-moo has gone to the super market to buy chocolates for his friends. He entered a shop and found that they sell many boxes of chocolates. All the chocolate boxes are lined up on the display and there are exactly N (0 < N <= 100000) chocolate boxes. The i-th number box contains Ai (0 < Ai <= 100000) amount of chocolates inside. Choco-moo loves chocolates and wants to buy all of the boxes, but he won’t. He will only buy boxes that contains amount of chocolates that can be divided by K (0 < K <= 100000) since he has K number of friends and wants to divide the chocolates equally without wasting any chocolates.

Now, you are given the value N and then N numbers indicating the amount of chocolates inside the N boxes. You have to answer some queries for Choco-moo. You will be given Q (0 < Q <= 100000) queries.

In each query, Choco-moo will provide you with three integers, A, B  (0 < A<=B <= N) and K. Here A and B are index number and K is the number of friends Choco-moo has. Now you have to find how many chocolate boxes Choco-moo can buy between Ath box to Bth box (inclusive)?

Input

The first line contains an integer T (T<=2), which is the number of test cases.

Each test case starts with a number N. After that N positive numbers follow indicating amount of chocolates inside each box. After that an integer Q is provided indicating number of queries to be answered. Each query has three integers, A, B and K. The ranges of the variables are described in the description.

Output

For each test case, print case number (Check sample output) and then for every query print the number of chocolate box Choco-moo can buy for his K friends from Ath box to Bth box (inclusive) in a newline.

Example

Input:

2

5

1 2 3 4 5

2

1 5 1

1 5 2

5

12 32 5 12 9

3

1 5 2

3 5 3

2 5 2

Output: 

Case 1:

5

2

Case 2:

3

2

2

 

Explanation: In Case 1: Query 1 Choco-moo buys all the boxes since all boxes are divisible by 1. In query 2 he buys second and fourth box since they are divisible by 2 ( 2 and 4 ).

Note: Let me know if you think the judge data is weak or there is ambigutiy/mistake in the problem statment. 


Added by:forthright48
Date:2013-09-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-02-03 19:52:14 Rang
Be extra careful about the presentation!!! .. wasted a lot of time there! :-(
2014-11-08 22:04:42 Venkatesh Ganesan
Very weak test cases.
My second AC solution should TLE like mad.

Last edit: 2014-11-08 22:06:54
2014-09-29 18:44:41 andre schurrle
Any hints on how to solve this problem.
2014-03-29 17:57:09 SanchitK
my code gives segmentation error. please help.
2013-12-27 09:01:23 (^-^)
test cases appears to be weak my AC solution gives tle on a similar question
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.