You are given an array of N integers: A1, A2, . . . , AN . You have to process Q queries on this array, where a query will be a pair of integers (L, R). For each query, you have to find the count of Divisor-free numbers in the number sequence S, where S = AL, AL+1, . . . , AR. A number Ai from the sequence S will be called Divisor-free if there is no Aj (i̸=j)inSsuchthatAj isadivisorAi. Input The first line of the input contains an integer T (T ≤ 5) denoting the number of test cases. The first line of each test case contains two integers N and Q (1 ≤ N, Q ≤ 105). The following line contains N space separated integers A1, A2, ..., AN where 1 ≤ Ai ≤ 106. In each of the next Q lines, there will be two integers (L, R) representing a query (1 ≤ L ≤ R ≤ N ). Output For each test case, print the case number in the format ‘Case X:’ (here, X is the serial of the test case). Then print Q lines containing the answer for each query. Sample Input 2 10 5 4 6 2 7 5 11 14 21 13 2 26 48 28 37 49 53 46815 15 23 33 Sample Output Case 1: 4 3 4 4 4 Case 2: 1 2 1