## FRQPRIME - Frequent Prime Ranges

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

**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

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 |