== include(page="template/taskheader" task_id="primesums") ==

You are given an integer $n$ and your task is to check how many numbers from $1$ to $n$ can be written as sum of $k$ not necessary distinct prime numbers.
 
As this is too easy, you will have to check whether this is possible or not for $q$ such numbers.

Poveste şi cerinţă...

h2. Date de intrare

The input file $primesums.in$ will consist of only one number $q$, representing the number of queries.
 
The next $q$ lines will consist of two integers $n$ and $k$

Fişierul de intrare $primesums.in$ ...

h2. Date de ieşire

The output file $primesums.out$ will consist of $q$ lines, each having a single element representing the answer of the problem.

În fişierul de ieşire $primesums.out$ ...

h2. Restricţii

* $1 ≤ q ≤ 10^5$
* $1 ≤ n ≤ 10^18$
* $3 ≤ k ≤ 10^9$
* For tests worth $10$ points, $q$ = $1$, $3 ≤ n, k ≤ 200$
* For tests worth $20$ more points, $q$ = $1$, $1 ≤ n, * k ≤ 10^6$
* For tests worth $30$ more points, $1 ≤ n ≤ 10^6$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. primesums.in |_. primesums.out |

| 4
7 3
10 4
11 5
7 4
| 2
3
2
0

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="primesums") ==