Special Pair

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

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