CF1603D Artistic Partition

对于两个正整数 $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）](https://en.wikipedia.org/wiki/Greatest_common_divisor)。 YouKn0wWho 有两个整数 $n$ 和 $k$，其中 $1 \le k \le n$。令 $f(n, k)$ 表示所有整数序列 $0=x_1 \lt x_2 \lt \ldots \lt x_{k} \lt x_{k+1}=n$ 的 $\sum\limits_{i=1}^{k}{c(x_i+1,x_{i+1})}$ 的最小值。 帮助 YouKn0wWho 找到 $f(n, k)$。

第一行包含一个整数 $t$ ($1 \le t \le 3 \cdot 10^5$) — 测试用例的数量。 每个测试用例的第一行也是唯一的一行，包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 10^5$)。

对于每个测试用例，打印一个整数 — $f(n, k)$。

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