NASPRIM  Tama Starks Prime Apprenticeship
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 bounderies L and R of a range, answer how many kpairs are there? kpair 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 kpair 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 kpairs (11, 13) and (17, 19) and if k = 4 in the same range then there is only one kpair (13, 17). Note that, (7, 11) and (19, 23) pairs are not within the boundary of the range and thus not kpairs 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 kpair.
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 kpairs 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
shravinson:
20180616 11:17:21
for L>R soln is 0 or swapping required????? 

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

absolute_coder:
20180614 19:15:33
swap l and r if l > r cost me Two WA Last edit: 20180614 19:15:53 

shravinson:
20180609 13:43:10
already check for L>R but still Wrong Answer.....


[Lakshman]:
20180608 15:09:55
can we count this as three different pairs (3, 5),(5 7),(11 13) for L= 1, R=13, K=2;


shravinson:
20180607 17:33:01
already check corner cases but still wrong answer in the 15th case, don't know why.........


Simes:
20180605 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.


yashkodesia:
20180604 01:28:21
I haven't heard a hack case this lame my whole life!


wisfaq:
20180603 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.


Avik Sarkar:
20180603 14:19:31
@nadstratosfer ... That was the Hack Case. If somethings is not clearly mentioned in the problem statement that means you need to consider those things.

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