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


be1035016:
20180603 12:57:19
never take nothing for granted;) 

nadstratosfer:
20180603 11:02:49
There's just 2 AC solutions out of 44 users in that contest, and over half submissions in here are WA. That's why I suspect some formatting issue where select IO method works and other don't. Please recheck or give a hint where my solution gives wrong answer.


Avik Sarkar:
20180603 08:00:06
Nope @ nadstratosfer . The judge file is OK. And it's been solved during contest. For assurance watch here: http://www.spoj.com/COUMAY17/ranks2/ 

nadstratosfer:
20180603 01:32:15
I think there might be something wrong with the testfiles. 
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 