Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Special Pair

By MosharrafOshy · Limits 1s, 512 MB

Mr. X is an “array pagla” person. He loves doing different types of things with arrays. Today Mr. X is going to his friend Sohel Hafiz’s birthday party. He took an array A with him as a birthday present. The present contains some arbitrary numbers and queries. It also contains some special pairs in it. Two numbers will be called a special pair if:

  • For any i , j (1 ≤ i ≤ j ≤ array_length), A[i] % A[j] = 0 and A[i] / A[j] > 1

Mr. X has met with you in that party. Being an “array pagla” person, he could not resist himself to give you the same array.

Now your task is, given an array and two numbers L, R (1 ≤ L ≤ R ≤ array_length), you have to find out the total number special pairs of the sub-array L to R.

Input

Input starts with an integer T (T ≤ 3), denoting the number of test cases.
Each case starts with a line that contains an integer N (1 ≤ N ≤ 10^4) and Q (1 ≤ Q ≤ 10^4), i.e. the length of the array and number of queries. The next line will contain N integers separated by spaces which denote the elements of the array A[i] (1 ≤ A[i] ≤ 40). Next Q lines will contain two numbers each L and R (1 ≤ L ≤ R ≤ N).

Output

At first print test case number just like sample output “Case X:”, where X is the test case number. For the next Q lines print an integer which denotes the special pairs of sub-array L to R.

Sample

InputOutput
2

4 2
2 1 10 5
1 2
3 4

3 1
2 2 2
1 3
Case 1:
1
1
Case 2:
0

Discussion

Statistics


13% Solution Ratio

bqi343Earliest, Aug '16

AungkurFastest, 0.3s

RobbinLightest, 876 kB

bqi343Shortest, 1045B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.