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.