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 ]