CF1603D.Artistic Partition

For two positive integers $l$ and $r$ ( $l \le r$ ) let $c(l, r)$ denote the number of integer pairs $(i, j)$ such that $l \le i \le j \le r$ and $\operatorname{gcd}(i, j) \ge l$ . Here, $\operatorname{gcd}(i, j)$ is the greatest common divisor (GCD) of integers $i$ and $j$ .

YouKn0wWho has two integers $n$ and $k$ where $1 \le k \le n$ . Let $f(n, k)$ denote the minimum of $\sum\limits_{i=1}^{k}{c(x_i+1,x_{i+1})}$ over all integer sequences $0=x_1 \lt x_2 \lt \ldots \lt x_{k} \lt x_{k+1}=n$ .

Help YouKn0wWho find $f(n, k)$ .

The first line contains a single integer $t$ ( $1 \le t \le 3 \cdot 10^5$ ) — the number of test cases.

The first and only line of each test case contains two integers $n$ and $k$ ( $1 \le k \le n \le 10^5$ ).

For each test case, print a single integer — $f(n, k)$ .

In the first test case, YouKn0wWho can select the sequence $[0, 2, 6]$ . So $f(6, 2) = c(1, 2) + c(3, 6) = 3 + 5 = 8$ which is the minimum possible.