**Problem:**↵
<br> <br>↵
A certain strange mathematician, Rasyak, considers a particular set of prime numbers beautiful. He also calls a composite number beautiful, if it is divisible by at least one prime number in his chosen set of beautiful primes. Given Rasyak’s set of M beautiful primes and an integer N, you have to find the number of beautiful numbers (both primes and composites) between 1 and N. For example, given a set of 2 beautiful primes, {2, 5}, there are 6 beautiful numbers between 1 and 10 (i.e. 2, 4, 5, 6, 8 and 10).<br><br>↵
**Input**<br>↵
The first line of the input gives the number of test cases, T (1 <= T <= 100). T test cases follow. Each will consist of one line containing a single integer M, followed by a line containing M space-separated prime numbers mi, followed by another line containing a single integer N.<br>↵
1 <= M <= 25<br>↵
1 <= mi <= 1000<br>↵
1 <= N <= 2*10^9<br> <br>↵
**Output**<br>↵
For each test case, output one line containing a single integer X, where X is the number of beautiful numbers between 1 and N.<br>↵
_**Input**_↵
3↵
2↵
2 5↵
10↵
3<br>↵
3<br>↵
2<br>↵
2 5<br>↵
10<br>↵
3<br>↵
2 5 13<br>↵
100↵
25<br>↵
25<br>↵
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97<br>↵
2000000000<br><br>↵
_**Output**_↵
6↵
63↵
1759360857↵
↵
↵
<br>↵
6<br>↵
63<br>↵
1759360857<br>↵
<br>↵
<br>↵
I know this can be solved with inclusion-exclusion principle. But,<br>↵
How do I implement this.↵
<br>↵
please help me with implementing this in C/C++↵
<br>↵
It is already in [this](http://codeforces.net/blog/entry/21889) blog .. but it has only an answer saying about th inclusion-exclusion principle ..↵
<br> <br>↵
A certain strange mathematician, Rasyak, considers a particular set of prime numbers beautiful. He also calls a composite number beautiful, if it is divisible by at least one prime number in his chosen set of beautiful primes. Given Rasyak’s set of M beautiful primes and an integer N, you have to find the number of beautiful numbers (both primes and composites) between 1 and N. For example, given a set of 2 beautiful primes, {2, 5}, there are 6 beautiful numbers between 1 and 10 (i.e. 2, 4, 5, 6, 8 and 10).<br><br>↵
**Input**<br>↵
The first line of the input gives the number of test cases, T (1 <= T <= 100). T test cases follow. Each will consist of one line containing a single integer M, followed by a line containing M space-separated prime numbers mi, followed by another line containing a single integer N.<br>↵
1 <= M <= 25<br>↵
1 <= mi <= 1000<br>↵
1 <= N <= 2*10^9<br> <br>↵
**Output**<br>↵
For each test case, output one line containing a single integer X, where X is the number of beautiful numbers between 1 and N.<br>↵
_**Input**_
3↵
2↵
2 5↵
10↵
3
3<br>↵
2<br>↵
2 5<br>↵
10<br>↵
3<br>↵
2 5 13<br>↵
100
25
25<br>↵
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97<br>↵
2000000000<br><br>↵
_**Output**_
6↵
63↵
1759360857↵
↵
↵
6<br>↵
63<br>↵
1759360857<br>↵
<br>↵
<br>↵
I know this can be solved with inclusion-exclusion principle. But,<br>↵
How do I implement this.
please help me with implementing this in C/C++
It is already in [this](http://codeforces.net/blog/entry/21889) blog .. but it has only an answer saying about th inclusion-exclusion principle ..↵
