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)$.

对于两个正整数 $l$ 和 $r$（满足 $l \le r$），定义 $c(l, r)$ 为满足 $l \le i \le j \le r$ 且 $\operatorname{gcd}(i, j) \ge l$ 的整数对 $(i, j)$ 的个数。其中，$\operatorname{gcd}(i, j)$ 表示整数 $i$ 与 $j$ 的最大公约数（GCD）。

YouKn0wWho 有两个整数 $n$ 和 $k$，满足 $1 \le k \le n$。定义 $f(n, k)$ 为对所有满足 $0 = x_1 < x_2 < \ldots < x_k < x_{k+1} = n$ 的整数序列，表达式 $\sum\limits_{i=1}^{k}{c(x_i+1,x_{i+1})}$ 的最小值。

请帮助 YouKn0wWho 求出 $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$).

第一行包含一个整数 $t$（$1 \le t \le 3 \cdot 10^5$）—— 测试用例的数量。

每个测试用例仅有一行，包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 10^5$）。

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

对于每个测试用例，输出一个整数——$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.

在第一个测试用例中，YouKn0wWho 可以选择序列 $[0, 2, 6]$。因此 $f(6, 2) = c(1, 2) + c(3, 6) = 3 + 5 = 8$，这是可能的最小值。