NASPRIM - Tama Starks Prime Apprenticeship

no tags 

Tama Stark loves to learn new things. He took the apprenticeship of Shakil Tarly who is a master of CP3. His master recently taught him about prime numbers. A prime number is a number that is only divisible by 1 and itself (i.e. 2, 3, 5, 7, 11 ...). Then Tama Stark started learning about many different properties of prime numbers. But after a while he began to think that he had learned everything about prime numbers. So his master decided to test him with the following problem:

Given the boundaries L and R of a range, answer how many k-pairs are there? A k-pair is defined as a pair of numbers (p, p+k) where p and p+k are both prime numbers. In this problem, (p, p+k) is a k-pair between the boundary of L and R if both p and p+k are prime numbers and inside the boundary of L and R (inclusive). For example, if the L = 10 and R = 20 and k = 2 then there are two k-pairs (11, 13) and (17, 19) and if k = 4 in the same range then there is only one k-pair (13, 17). Note that (7, 11) and (19, 23) pairs are not within the boundary of the range and thus not k-pairs in this case.

Tama Stark is currently busy with his new interest python charming! But he also wants to continue his apprenticeship to Shakil Tarly. Can you help him solve the problem?

Input

First line of the input will contain an integer T, the number of test case. T lines will follow. Each line will have three space separated integers L R k where L and R denotes the boundary of the range and k is the difference between the numbers of k-pair.

Constraints

T <= 300

1 <= L, R, k <= 10000000

Output

For each test case, output a single integer N in a line where N is the number of k-pairs as described in the problem stated above.

Example

Input:
2
10 20 4
10 20 2

Output:
1
2

[ Original setter of this problem is Nasif Mahbub, RUET ]


hide comments
hodobox: 2019-08-10 08:03:30

Test cases are extremely weak - the numbers T,L,R and k are ALWAYS given in base 10, when this is not clearly mentioned in the statement!

shravinson: 2018-06-16 11:17:21

for L>R soln is 0 or swapping required?????

spaceman_spiff: 2018-06-14 23:35:47

@shravinson : Look at the edge cases. One possible line of thought could be what's different about prime(s).

absolute_coder: 2018-06-14 19:15:33

swap l and r if l > r cost me Two WA

Last edit: 2018-06-14 19:15:53
shravinson: 2018-06-09 13:43:10

already check for L>R but still Wrong Answer.....

=>(Avik)=> Then there must some other problem.

Last edit: 2018-06-12 14:43:33
[Lakshman]: 2018-06-08 15:09:55

can we count this as three different pairs (3, 5),(5 7),(11 13) for L= 1, R=13, K=2;

=> ( Avik ) => Yes

Last edit: 2018-06-09 04:31:26
shravinson: 2018-06-07 17:33:01

already check corner cases but still wrong answer in the 15th case, don't know why.........
looks like some problem in cases

=>(Avik) => Check for cases like L>R .

Last edit: 2018-06-07 21:55:53
Simes: 2018-06-05 06:33:30

To call the ends of the ranges L and R, with the implied meaning of Left and Right, and then not have them actually mean that, is plain nasty. At the very least, there should be an example like that in the sample inputs.

=>(Avik)=> L and R is range notation . It's nowhere said that L will always be less than R and all that.

Last edit: 2018-06-07 21:55:07
yashkodesia: 2018-06-04 01:28:21

I haven't heard a hack case this lame my whole life!
Deception level 1/0.

=>(Avik Sarkar)=> May be you didn't face this type of problem in your whole life. But we faced. And want other should face. Cause from beginning we have learned that while designing an algorithm you should keep every aspect in your mind.

Last edit: 2018-06-04 04:39:26
wisfaq: 2018-06-03 15:09:06

It's also not clearly stated that the first two of L R k are L and K or K and L.
There are in total 6 permutations of L, R and k possible. So we should guess which is the correct one?
What should 100 10 1000 mean? L=100, R=1000 and k=10 perhaps?

=>(Avik Sarkar) => Watch the input section carefully. You can see L, R, k is given sequentially. And also their denotation is also given sequentially.

Last edit: 2018-06-15 09:33:22

Added by:Avik Sarkar
Date:2018-05-30
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:RUET Beginner Battle -1