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 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?
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.
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 |
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
|