Hazzat is a new guys in computer science. Now he read in 3rd semester. Recently he completed the course data structure. After finished data structure course he can realize that those are not enough for his. Every day he fall in a new (data structure) problem and want solve it, but those problem he can’t solve using his know data structure. He want to establish new data structure. But he always failed to establish it. Now help Hazzat to establish a new data structure following problems.

You will be given an array A of N integers. You need to answer M queries.

Each query is of the form V x y.

For each query, find the sum of set S which is a sub set of array A index x to y and fully divisible by V.

That means find sum of set S (subset of A), where A[i] is included in S if x ≤ i ≤ y and A[i] % V == 0.

Input

First line consists of a number T (1 ≤ T ≤ 5) test cases.

For each case given two integer number N M (1 ≤ N ≤ 10^5, 1 ≤ M ≤ 2*10^5)

Next line has N integers representing the elements of array A. (1 ≤ A[] ≤ 10^6)

M lines follow, one per query.

Each line has 3 integers V, x and y (1 ≤ V ≤ 1000, 1 ≤ x ≤ y ≤ N)

Output

For each case print case number and query answer.

Write a blank line between two cases.

Sample

Input
2
5 2
1 2 3 4 6
2 1 5
5 1 4
5 2
2 3 5 3 7
3 2 4
5 1 5

Output
Case #1
12
0

Case #2
6
5

Hints:

Query 1: in array index 1 to 5 the set S is {2, 4, 6} because those are fully divisible by 2, so the sum is 12.

Query 2: in array index 1 to 4 the set S is { } because there are not any number which fully divisible by 5, so the sum is 0.

Data set is so huge. Use faster I/O