ABA12D  Sum of divisors!
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 Knumbers.
Given a range [A,B] you are expected to find the number of Knumbers in this range.
Input
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
Output T lines each containing a single integer ‘c’ which denotes the number of Knumbers which lie in the interval [A,B] inclusive of the end points.
Constraints:
1<=T<=10000
1<=A<=B<=10^6
Example
Input: 2
1 5
9 10
Output: 2
1
Explanation of sample case:
1) In the range [1,5] the Knumbers are 2 and 4 because
Divisors of 2 are 1 and 2 which sum up to 3, which is a prime.
Divisors of 4 are 1,2 and 4 which sum up to 7, which is a prime.
2) The Knumber in the range [9,10] is 9.
hide comments
sarthak_19:
20191028 03:54:04
nice logic :) 

prudhvi_495:
20190511 20:44:09
My 100th ^..^ 

kspoj:
20171130 09:21:22
hardcoded :( 

sahil070197:
20171124 09:21:34
It's really nice :)


sonudoo:
20170615 16:24:43
I factorized only the numbers which are perfect squares. There has to be a better way to solve this.. 

tusharuppal:
20170614 11:43:50
easy one...AC in one go ;) 

adm2215:
20170410 19:55:17
Implemented brute force approach but got TLE , eventually hard coded . ;(( 

amulyagaur:
20170316 10:24:54
https://oeis.org/A023194 

cake_is_a_lie:
20170306 02:49:13
Rather than say "If you really want to learn something by solving this problem, don't hard code!", you might as well have increased the time limit to ~3s and the query limit to 10^12; that would have made hardcoding without the proper solution impractical. 

coder_hsnake:
20170201 15:08:57
can take help from

Added by:  Kashyap Krishnakumar 
Date:  20120113 
Time limit:  0.103s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC ASM64 MAWK BC CCLANG CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own problem 