I have a friend named Hippo. Hippo is my best friend. Whenever I am happy I call hippo. Whenever I am sad I call hippo. I call hippo even if I am not happy or sad. Hippo means a lot to me. So if hippo is in some sort of trouble and asks me for help I would do anything to solve that problem. You might find it interesting that hippo is a very good programmer too. Hippo likes to solve difficult and challenging problems. We have been solving problems from the beginning of our friendship. So if anyone is facing some difficulties getting Accepted in some problem the other person always tries to help. Yesterday, hippo gave me a code and asked me if the code is alright. Hippo told me that the code was getting the verdict Time limit ex- ceeded again and again. So I asked about the problem. Let me tell you the problem exactly like hippo described: An integer N is given. You need to find out how many numbers I (1 ≤ I ≤ N) are there such that GCD(I,N) ≤ X. Here GCD means greatest common divisor. Now being super busy with your contest, I have no time to help my friend. But I cant let hippo feel helpless with any problem. So can you please help hippo and save our friendship? Input The first line of input is an integer T (1 ≤ T ≤ 10), which is the number of test cases. Each case starts with two integers N (0 < N ≤ 1012) and Q (0 < Q ≤ 50,000). After that Q lines follow, each with a value of X, which will be a 64 bit signed integer. Output For each case print a line ‘Case C’ (without the quotes), where C is the case number. After that for each X print a line with the value R, where there are R positive numbers less than or equal to N such that their GCD is less than or equal to X. Explanation of 1st Sample Input For 1, 7, 11, 13, 17, 19, 23, 29 the GCD with 30 is 1. For 2, 4, 8, 14, 16, 22, 26, 28 the GCD with 30 is 2. GCD (30,15) = 15. All the other values have GCD ≤ 10. Sample Input 2 30 3 1 2
2/2 10 11 2 1 2 Sample Output Case 1 8 16 28 Case 2 10 10