SNGPG - Prime Generator The Easiest Question Ever

no tags 

Prime number questions are always being favorite to everyone. This question is extension to the problem PRIME GENERATOR. The question is very very simple and easier than that you cannot imagine. You have to count total number of such primes p in the range [a ≥ 0, b > 0] so that (p2 + 1) or/and (p2 + 2) is/are prime(s).

Input

First line of input is t, (t < 100) total number of test cases. Next t lines contains two integers a and b separated by space.
a < 50001, b < 100001 and b > a.

Output

In each line print total numbers of such prime numbers.

Example

Input:
2
0 1
4 5 Output: 2
0

[Consider 0 and 1 as prime numbers for this question]


hide comments
vibhubhatia: 2019-12-13 12:07:01

if p>=5 is a prime number, then p^2 +2 is a composite........that's all

mriow: 2019-08-14 12:50:23

Easy to solve intuitively in O(1) for every test case...
Or even by a pseudo naive solution using the " segmented sieve of eratosthenes" in O(sqrt(b))...

HOWEVER, to really prove the O(1) solution you will need:
- Modular arithmetic
- Fermat's little theorem / Euler's theorem

Last edit: 2019-08-14 14:34:07
wolfie10: 2019-05-19 18:32:20

try implementing functions!!
easy problem..good for beginners!

mag1x_: 2018-06-22 13:45:24

When all you require is pen & paper :)

rajcoolaryan: 2018-06-20 09:46:59

0.00 AC.. 2 lines of code

dushyant_bgs: 2016-06-27 19:48:42

Just observe and get 0.00s. :-)

mkfeuhrer: 2016-06-18 22:49:28

took less than 15 min to solve and code !! tutorials -->

akshayvenkat: 2016-05-10 11:51:10

NotUsingPenAndPaper Solution - 0.81s
UsingPenAndPaper Solution- 0.00s

aditya1997: 2016-02-12 12:08:45

easiest question ever!!!! my 50 th :)

Siddharth Singh: 2015-12-26 06:53:52

Though i got an AC , i'm still confused because if i giv input 0 9 it gives me ans of 4
instead of 5
and still it is AC

Last edit: 2015-12-26 06:54:16

Added by:AvmnuSng
Date:2013-09-08
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Abhimanyu Singh
My Problems