KPRIMESB  Almost Prime Numbers Again
Almost Prime Numbers are composite numbers which are not divisible by certain prime numbers. Given K prime numbers and an integer N, find out the number of Almost Prime Numbers (ie. composite numbers not divisible by any of the given K prime numbers) that are not greater than N.
Input
First line of input consists of an integer T (1<=T<=1000), denoting the number of test cases. Then T test cases follow. Each case begins with a line containing two integers N (0<=N<=10^6) and K (1<=K<=10). The next line contains K space separated prime numbers. All the prime numbers are guaranteed to be less than 50.
Output
For each test case, output a single line in the format Case X: Y, where X denotes the test case number and Y denotes the number of Almost Prime Numbers that are not greater than N.
Example
Input: 2 1000 3 2 3 5 49 3 2 3 5
Output: Case 1: 100 Case 2: 1
hide comments
yaseenmollik:
20200413 00:00:26
Solved it using InclusionExclusion Principle!!


nimphy:
20180429 05:36:07
@ mehmetin ，really？ 

chandan pandey:
20170703 20:52:46
Any approach other than Exclusion inclusion ?? 

Bhuvnesh Jain:
20161012 16:07:42
Why include "n = 0"? Easy one though. 

fR0DDY:
20160702 21:18:14
It was a silly integer overflow. :( Last edit: 20160703 03:31:14 

HM Mehrab:
20160418 08:43:04
There are others who have solved this problem, and well within the time limit I should add. So if your algorithm gets TLE, you should try to improve it. And there is no guarantee that all test cases are distinct. The worst case may appear many times in the test data. 

farhan764:
20160417 12:02:34
hey PS, my solution is giving all possible answer within .25 sec..........then why am i getting tle...can u plz check 

erlanggakm:
20160415 05:18:33
imho, case 2 : 2; its 25 and 49 since Almost Prime Numbers are not greater than N 

HM Mehrab:
20160401 19:16:31
I can't come up with an efficient solution to those constraints. If you want those constraints, you'll have to make the problem yourself lol Last edit: 20160401 21:50:28 

mehmetin:
20160401 18:42:56
A still harder version is possible (for example N<=10^9, K<=1000, T and time limit can be chosen accordingly) 
Added by:  HM Mehrab 
Date:  20160401 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 