BUET Inter-University Programming Contest

Problem B – Best Friend

 

Problem

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.

https://lh5.googleusercontent.com/SxhBlS4U9H7BHD7wEZJBQMOg-oMYKj7v3DjUXnP3Lo3dlRSi__IhIj_iGWjNlFM5z5LPKM57jF_MH8mMVvslk3oAxBbF0Nt0yqMBmqCX-ecuZ6573ow

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 exceeded” 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  are there such that . Here GCD means greatest common divisor.

Now being super busy with your contest, I have no time to help my friend. But I can’t 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 , which is the number of test cases. Each case starts with two integers N and Q . 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.

Sample Input

Output for Sample Input

2

30 3

1

2

10

11 2

1

2

Case 1

8

16

28

Case 2

10

10

 

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 .

 

Problemsetter:

Hasnain Heickal Jami

Special Thanks:

Anindya Das