对于两个正整数 $$$l$$$ 和 $$$r$$$ ($$$l \le r$$$) 令 $$$c(l, r)$$$ 表示整数对 $$$(i, j)$$$ 的数量,使得 $$$l \le i \le j \le r$$$ 和 $$$\operatorname{gcd}(i, j) \ge l$$$。这里,$$$\operatorname{gcd}(i, j)$$$ 是整数 $$$i$$$ 和 $$$j$$$ 的最大公约数 (GCD)。
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})}$$$ 的最小值。
帮助您知道谁找到 $$$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)$$$。
示例
输入 #1
4 6 2 4 4 3 1 10 3
输出 #1
8 4 6 11
注意
在第一个测试用例中,YouKn0wWho 可以选择序列 $$$[0, 2, 6]$$$。所以 $$$f(6, 2) = c(1, 2) + c(3, 6) = 3 + 5 = 8$$$ 这是可能的最小值。