KPRIMES - Almost Prime Numbers

no tags 

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: 2016-04-01 12:29:48

Here you go. The tougher version: http://www.spoj.com/problems/KPRIMESB/

mehmetin: 2016-03-28 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: 2016-03-28 13:49:47
Scape: 2016-03-27 22:23:03

This is too easy, should be moved to tutorial. Why not N <= 10^9, K <= 1000?

farhan764: 2016-03-27 13:17:49

using sieve algo it can be solve easily.......

lalit_nit: 2016-03-27 12:52:22

Reduce time limit...Accepted through bruteforce too....

HM Mehrab: 2016-03-27 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: 2016-03-27 09:47:27
mehmetin: 2016-03-26 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: 2016-03-26 11:11:07

Added by:imranziad
Date:2016-03-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:IAPC Round #1 - H.M. Mehrab