প্রায় মৌলিক সংখ্যা ( Almost Prime Numbers )

CPU: 1s
Memory: 1024MB


“প্রায় মৌলিক সংখ্যা” হচ্ছে সেইসব যৌগিক সংখ্যা যারা শুধুমাত্র একটি মৌলিক সংখ্যা দিয়ে বিভাজ্য। এই প্রশ্নে তোমাকে এমন একটি কার্য পদ্ধতি (প্রোগ্রাম) লিখতে হবে যা একটি নির্দিষ্ট পরিসরের মধ্যে কতগুলো “প্রায় মৌলিক সংখ্যা” আছে তা বের করতে পারে।

Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.


ইনপুটের বর্ণনা

ইনপুট ফাইল এর প্রথম লাইন এ থাকবে একটি পূর্ণ সংখ্যা N (N <=৬০০) যা ফাইল এ কতগুলো ইনপুট সেট আছে তা বুঝাবে। এর পরের প্রতিটি লাইন একটি সেটের ইনপুট কে ধারণ করবে। প্রতি লাইন এ থাকবে দুটি পূর্ণ সংখ্যা low এবং high (০ < low <= high < ১০^১২ ).


Input Specification

First line of the input file contains an integer N (N <= 600) which indicates how many sets of inputs are there. Each of the next N lines make a single set of input. Each set contains two integer numbers low and high (0 < low <= high < 10^12).


আউটপুট এর বর্ণনা

প্রথম লাইন ব্যতিত অন্য সকল ইনপুট লাইনের জন্য এক লাইন আউটপুট দিতে হবে। এই লাইনে একটি পূর্ণ সংখ্যা থাকবে যা low থেকে high এর মধ্যে (low এবং high কেও বিবেচনা করতে হবে /inclusive) কতগুলো "প্রায় মৌলিক সংখ্যা" আছে তা নির্দেশ করবে।


Output Specification

For each line of input except the first line you should produce one line of output. This line contains a single integer, which indicates how many almost prime numbers are within the range (inclusive) low…high.


Sample

InputOutput
3 1 10 1 20 1 53 4 1