FRQPRIME - Frequent Prime Ranges


A range [L..H] is called a K-Frequent Prime range if there are atleast K primes amongst the numbers L,L+1,..,H. Given N and K, calculate how many subranges of the range [2..N] are K-Frequent Prime.

Input

The first line contains the number of test cases T. Each of the next T lines contains 2 integers N and K.


Output

Output T lines, one corresponding to each test case, containing the required answer.

Example


Sample Input :
4
2 1
5 2
5 1
9 3

Sample Output :
1
4
9
8

Note : For the first test case, the only valid subrange is [2..2], whereas for the second test case, the valid subranges are : [2..3],[2..4],[2..5],[3..5].

Constraints

1 <= T <= 100

2 <= N <= 100000

0 <= K <= 10000


hide comments
sushantgokhale: 2017-04-25 11:32:39

Because I couldnt compute n(n-1)/2 directly, got 7-8 times WA. Disgusting :|

Just go on adding 'n' to sum (n-1) times.

sushantgokhale: 2017-04-25 10:52:33

@Varun.

When I try to perform following action:
long long num = 100000 * (100000-1);
cout<<num<<endl;

following is the O/P on codechef:
1409965408


But wwhen I do:
long long num = 100000000000;
cout<<num<<endl;

it gives:
100000000000

Also, the size of long long is 8 bytes which is
1.8446744e+19
Any idea? I have got WA multiple times due to this :(

Last edit: 2017-04-25 10:58:44
rajeev_899: 2017-03-14 17:11:26

No Need Of Binary Search....Think Simple

shahzada: 2017-03-12 13:24:50

use long long ...costed me 2 WA.

aman224: 2017-02-20 14:45:01

O(pi(N)) , where pi(N) is the number of primes in [2...N]
No binary search required.

Last edit: 2017-02-21 03:21:24
Anand: 2017-01-24 07:39:48

not casting n to long while division costed me 4 WA

kp: 2015-06-19 14:35:07

use long for answer ! 1 WA :(

Sudarshan K: 2014-12-27 09:38:28

Super problem. :) No need for using extra memory. Binary Search is beautiful :)

Daga: 2014-10-08 00:18:30

Enjoyed

Arvind: 2014-10-01 11:25:09

Awesome Problem ... Simple Binary Search...

Last edit: 2014-10-01 11:25:38

Added by:Varun Jalan
Date:2010-01-25
Time limit:0.340s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem used for Technovanza