FRQPRIME  Frequent Prime Ranges
A range [L..H] is called a KFrequent 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 KFrequent 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
smso:
20200522 07:32:25
sieve + prefix sum + brute force 

ashok_shaun:
20191112 11:54:29
is binary search "THE OMNIPOTENT"? 

sushantgokhale:
20170425 11:32:39
Because I couldnt compute n(n1)/2 directly, got 78 times WA. Disgusting :


sushantgokhale:
20170425 10:52:33
@Varun.


rajeev_899:
20170314 17:11:26
No Need Of Binary Search....Think Simple 

shahzada:
20170312 13:24:50
use long long ...costed me 2 WA. 

aman224:
20170220 14:45:01
O(pi(N)) , where pi(N) is the number of primes in [2...N]


Anand:
20170124 07:39:48
not casting n to long while division costed me 4 WA 

kp:
20150619 14:35:07
use long for answer ! 1 WA :( 

Sudarshan K:
20141227 09:38:28
Super problem. :) No need for using extra memory. Binary Search is beautiful :) 
Added by:  Varun Jalan 
Date:  20100125 
Time limit:  1s 
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 