Problem Description

Pty thinks prime numbers are extremely annoying numbers. Specifically, he hates the first k prime numbers.

As ”Hate me Hate my dog.” , if one prime factor of the integer x is what Pty hates, Pty will also hate x.

Now Pty wants to know how many integers in [1,n] he dosen’t hate.

Formally, Pty wants to know $\sum_{x=1}^n$[$\forall$$i$$\in$$[1,k],p[i]$$\nmid$$x$] (p[i] means the $i^{th}$ prime number) .

Input

The first line contains a single integer T(1 ≤ T ≤ 100000) — the number of test cases

The only line of each test case contains two integers n,k(1 ≤ n ≤ $10^{18}$,1 ≤ k ≤ 16).

Output

For each test case, output the number of integers Pty doesn’t hate.

5
10 1
20 2
30 3
40 4
50 5

5
7
8
9
11