ABA12D - Sum of divisors!

**注意：如果你真的想通过这道题来学些东西，不要打表！ 这背后有一套美妙的逻辑！** --- ### 题目描述 Kartheeswaran 最近正在阅读一篇关于“完美数”的文章。完美数是指约数之和等于原数的两倍的数字。他对他们很感兴趣，并决定求出它们。但令他失望的是，这种数非常稀有。因此，他决定寻找与数字的约数之和相关的其他性质。 什么数字比质数更有趣呢？他决定留意那些 约数之和是质数 的数字，他叫它们 K-number。 给定闭区间 $[A, B]$，输出此区间内 K-number 的个数。 ### 输入格式 输入的第一行为一个整数 $T$，表示数据组数。 接下来的 $T$ 行，每行两个整数 $A, B$，含义如题目描述所示。 ### 输出格式 输出共 $T$ 行，每行包含一个整数 $C$，表示闭区间 $[A, B]$ 内 K-number 的个数。 ### 数据规模与约定 $ 1 \le T \le 10000 $ $ 1 \le A \le B \le 10^6 $

**Note:** **If you really want to learn something by solving this problem, don't hard code!** **There is a nice logic behind this!** \--- Kartheeswaran was recently reading an article on perfect numbers, whose sum of divisors equals twice the number. He was intrigued by them and decided to generate them but to his disappointment they turned out to be quite rare. So he decided to look out for a different property related to sum of divisors. What is more interesting than a number being a prime? So he decided to look out for numbers whose sum of divisors is a prime number and he was the inventor of these special numbers he gave them the name K-numbers. Given a range \[A,B\] you are expected to find the number of K-numbers in this range.

The first line of input indicates the number of test cases T. Then in the following T lines there will be a pair of integers A and B.

Output T lines each containing a single integer ‘c’ which denotes the number of K-numbers which lie in the interval \[A,B\] inclusive of the end points. Constraints: 1<=T<=10000 1<=A<=B<=10^6

2
1 5
9 10

2