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

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

 < Previous 1 2 3 Next > vishalshrm539: 2020-10-05 17:06:34 Sieve + Binary Search smso: 2020-05-22 07:32:25 sieve + prefix sum + brute force ashok_shaun: 2019-11-12 11:54:29 is binary search "THE OMNIPOTENT"? 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<