Sarthak and his Set of Primes solution codechef- 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.

Sarthak and his Set of Primes solution codechef

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

  • 1T21≤T≤2
  • 1N201≤N≤20
  • 1M10161≤M≤1016
  • 2Si<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 113355 and 99.

Leave a Comment

Your email address will not be published.