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 K-numbers.

Given a range [A, B] you are expected to find the number of K-numbers 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 K-numbers 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

1) In the range [1, 5] the K-numbers 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 only K-number in the range [9, 10] is 9.


Added by:Kashyap Krishnakumar
Date:2012-01-13
Time limit:0.103s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own problem

hide comments
2016-01-13 09:07:14
People facing tle try upper_bound and lower_bound c++ stl functions..
2016-01-09 11:09:41
can any1 please tell me the logic please?
i solved it hardcore just for fun.....but there is no point doing this without logic.
plz help (:
2015-11-26 16:29:34
guys , i'm getting wrong answer every time but on my local machine it's working...
any suggestions please.
2015-09-03 11:51:57 noob909
what is the logic ?? please mail me no.sharing@cheating.com

Last edit: 2023-02-03 23:11:20
2015-08-23 22:27:33 Utkarsh
Anyone with the actual logic please mail me at utkarshg1408@gmail.com
I've spent 2 days on this question :( No satisfaction -_-
2015-06-29 10:17:59
is using OEIS and getting AC a legitimate way to solve this???
2015-05-29 11:39:48 Aditya Kumar
Use fastest I/O and also use unsigned data types for faster execution.
2015-05-12 08:50:06 Gohan
The languages should include C++11 or C++14!
Got a CE as C++ requires math.h for sqrt()
C++11 doesn't!
2015-04-16 23:53:00 xMAn
my 50th :D
2015-04-10 22:56:52 krish
Good Problem:)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.