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 bounderies L and R of a range, answer how many k-pairs are there? 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
Avik Sarkar: 2018-06-03 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.
At least while doing contest we keep this line in our mind.

be1035016: 2018-06-03 12:57:19

never take nothing for granted;)

nadstratosfer: 2018-06-03 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.

Edit: So I wasted 1.5 hours on Saturday evening because psetter's idea of range includes L > R. Also thanks for nothing to those that got AC yet didn't bother to point it out. Twats.

Last edit: 2018-06-03 13:24:29
Avik Sarkar: 2018-06-03 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: 2018-06-03 01:32:15

I think there might be something wrong with the testfiles.


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