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
Daga:
20141008 00:18:30
Enjoyed


Arvind:
20141001 11:25:09
Awesome Problem ... Simple Binary Search... Last edit: 20141001 11:25:38 

Massand Sagar Sunil:
20130607 21:07:11
Could you please explain test case 3?Shouldn't the answer be 8?


vimal raj sharma old account:
20100219 17:40:21
@ Siarhei Khamenka


Siarhei Khamenka:
20100219 13:31:21
got the same, but did you test K=0 ? 

vimal raj sharma old account:
20100212 03:50:56
can anyone tell me the output for


Ehor Nechiporenko:
20100128 10:10:27
Beware! Answer may not fit in 32bit integer. 
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 