## KPRIMESB - Almost Prime Numbers Again

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 (i.e. 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```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 1e6+5;

bool isPrime[MAXN];
void sieve(){
isPrime[0] = isPrime[1] = 1;
for(int i = 2;i*i <= 1000000; i++){
if(!isPrime[i]){
if(i*1LL*i <= 1000000){
for(int j = i*i;j <= 1000000; j += i)
isPrime[j] = 1;
}
}
}
}

int matrix[MAXN];
int primes[55], n, k;

void solve(){
for(int i = 0;i <= n; i++)
matrix[i] = 0;

for(int i = 0;i < k; i++){
int num = primes[i];
for(int j = num;j <= n; j += num){
matrix[j] = 1;
}
}
}

int main(){
sieve();
int tc = 1;
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &k);
for(int i = 0;i < k; i++)
scanf("%d", &primes[i]);
solve();
int ans = 0;
for(int i = 2;i <= n; i++){
if(!matrix[i] && isPrime[i]){
ans++;
}
}
printf("Case %d: %d\n", tc, ans);
tc++;
}
return 0;
}``````
Copy The Code &

Input

cmd
2
1000 3
2 3 5
49 3
2 3 5

Output

cmd
Case 1: 100
Case 2: 1