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.