FRQPRIME  Frequent Prime Ranges
A range [L..H] is called a KFrequent Prime range if there are at least 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.
Constraints
1 <= T <= 100
2 <= N <= 100000
0 <= K <= 10000
Example
Input: 4 2 1 5 2 5 1 9 3 Output: 1 4 9 8
Explanation
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].
hide comments
vishalshrm539:
20201005 17:06:34
Sieve + Binary Search 

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 :( 
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 