Sarthak and his Set of Primes solution codechef
-
For Solution
Click Here!
Sarthak has a set SS of NN distinct prime numbers. He grew very fond of that set, and now he only likes a positive integer XX if all of its prime factors belong to SS. Given the set and a positive integer MM, can you find out how many integers he likes which are not more than MM?
Note: Sarthak always like the number 11.
Input Format Sarthak and his Set of Primes solution codechef
- The first line of each input contains TT – the number of test cases. The test cases then follow.
- The first line of each test case contains two space-separated integers NN and MM – the size of SS and the limit defined in the statement.
- The second line of each test case contains NN space-separated integers S1,S2,…,SNS1,S2,…,SN – the elements of SS.
Output Format
For each test case, output on a single line the number of positive integers Sarthak likes that is not more than MM.
Sarthak and his Set of Primes solution codechef Constraints
- 1≤T≤21≤T≤2
- 1≤N≤201≤N≤20
- 1≤M≤10161≤M≤1016
- 2≤Si<10002≤Si<1000
- SS has NN distinct prime numbers
Sample Input 1
1
2 10
3 5
Sample Output 1 Sarthak and his Set of Primes solution codechef
4
Explanation
- Test case 11: Sarthak likes the numbers 11, 33, 55 and 99.