CPU: 1s
Memory: 1024MB
রসায়কা নামের একজন অদ্ভুত গণিতবিদ নির্দিষ্ট কিছু মৌলিক সংখ্যাকে সুন্দর হিসেবে বিবেচনা করে। যদি কোন যৌগিক সংখ্যাকে তার পছন্দ করা সুন্দর মৌলিক সংখ্যাগুলির মধ্যে অন্তত একটি নিঃশেষে ভাগ করে, তাহলে সে ঐ যৌগিক সংখ্যাটিকেও সুন্দর মনে করে। রসায়কার পছন্দ করা M টি মৌলিক সংখ্যা এবং একটি পূর্ণসংখ্যা N দেওয়া থাকবে, তোমাকে 1 থেকে N এর মধ্যে কতটি সুন্দর সংখ্যা (মৌলিক এবং যৌগিক উভয়ই) রয়েছে, তা বের করতে হবে। উদাহরণস্বরূপ, 2 টি সুন্দর মৌলিক সংখ্যার সেট {2, 5} এর জন্য, 1 থেকে 10 এর মধ্যে 6 টি (2, 4, 5, 6, 8 এবং 10) সুন্দর সংখ্যা রয়েছে।
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).
ইনপুটের বর্ণনা
ইনপুটের প্রথম লাইনে টেস্টকেসের সংখ্যা T দেওয়া থাকবে। এর পরে T (1 <= T <= 100) টি টেস্টকেসের বর্ণনা থাকবে। প্রতিটি টেস্টকেসের প্রথম লাইনে একটি পূর্ণসংখ্যা M দেওয়া থাকবে এবং পরবর্তী লাইনে স্পেস দিয়ে আলাদা করা M টি মৌলিক সংখ্যা mi দেওয়া থাকবে এবং তার পরবর্তী লাইনে একটি পূর্ণসংখ্যা N থাকবে।
Input
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.
Note the following limits:
Dataset #1 (20 Pts)
1 <= M <= 10
1 <= mi <= 100
1 <= N <= 105
Dataset #2 (30 Pts)
1 <= M <= 17
1 <= mi <= 1000
1 <= N <= 108
Dataset #3 (50 Pts)
1 <= M <= 25
1 <= mi <= 1000
1 <= N <= 2*109
অাউটপুটের বর্ণনা
প্রতিটি টেস্টকেসের জন্য একটি লাইনে একটি পূর্ণসংখ্যা X আউটপুট দিতে হবে, যেখানে X হল 1 থেকে N এর মধ্যে যতটি সুন্দর সংখ্যা রয়েছে তার সংখ্যা।
Output
For each test case, output one line containing a single integer X, where X is the number of beautiful numbers between 1 and N.
Sample
| Input | Output |
|---|---|
| 3 2 2 5 10 3 2 5 13 100 25 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 2000000000 | 6 63 1759360857 |