FRQPRIME - Frequent Prime Ranges

A range [L..H] is called a K-Frequent 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 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.

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].


Added by:Varun Jalan
Date:2010-01-25
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

hide comments
2015-06-19 14:35:07 kp
use long for answer ! 1 WA :(
2014-12-27 09:38:28 Sudarshan K
Super problem. :) No need for using extra memory. Binary Search is beautiful :)
2014-10-08 00:18:30 Daga
Enjoyed
2014-10-01 11:25:09 Arvind
Awesome Problem ... Simple Binary Search...

Last edit: 2014-10-01 11:25:38
2013-06-07 21:07:11 Massand Sagar Sunil
Could you please explain test case 3?Shouldn't the answer be 8?

Got it. Sorry for spamming

Last edit: 2013-06-07 21:14:30
2010-02-19 17:40:21 vimal raj sharma old account
@ Siarhei Khamenka

thanks bro

actually i was testing but for ranges with exactly 0 primes

:-)


Last edit: 2010-02-19 18:57:03
2010-02-19 13:31:21 Siarhei Khamenka
got the same, but did you test K=0 ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.