KPRIMES  Almost Prime Numbers
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<=100), denoting the number of test cases. Then T test cases follow. Each case begins with a line containing two integers N (0<=N<=10^4) and K (1<=K<=5). 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
HM Mehrab:
20160401 12:29:48
Here you go. The tougher version: http://www.spoj.com/problems/KPRIMESB/ 

mehmetin:
20160328 12:51:09
psetter should move this problem to tutorial and prepare another version with higher constraints. N<=10^9, K<=1000 seems fine. Last edit: 20160328 13:49:47 

Scape:
20160327 22:23:03
This is too easy, should be moved to tutorial. Why not N <= 10^9, K <= 1000? 

farhan764:
20160327 13:17:49
using sieve algo it can be solve easily....... 

lalit_nit:
20160327 12:52:22
Reduce time limit...Accepted through bruteforce too.... 

HM Mehrab:
20160327 06:39:32
The original problem was written with tougher constraints. But then the constraints were made easier for the 1st round of the contest. A tougher constraints version will appear in a future round of the contest. Last edit: 20160327 09:47:27 

mehmetin:
20160326 10:08:52
Nice problem, but the constraints are too low. Could be at least something like T = 1000, N <= 10^6, K <= 10. Last edit: 20160326 11:11:07 

chiragm23:
20160325 14:32:16
Last edit: 20160325 14:51:10 
Added by:  imranziad 
Date:  20160323 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  IAPC Round #1  H.M. Mehrab 