Artistic Partition

题意翻译

对于给定的正整数 $l\leq r$，定义 $c(l,r)$ 为满足下列条件的正整数对 $(i,j)$ 的数量： - $l\leq i\leq j\leq r$； - $\gcd(i,j)\geq l$。 给定正整数 $k\leq n$。对所有满足 $0=x_1 < x_2 < \cdots < x_k < x_{k+1}=n$ 的整数序列 $(x_1,...,x_{k+1})$，计算 $\sum_{i=1}^kc(x_i+1,x_{i+1})$ 的最小值。你需要回答 $T$ 组询问。 对全部数据，$1\leq T\leq 3\times 10^5$，$1\leq k\leq n\leq 10^5$。

题目描述

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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) 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) $ .

输入输出样例

输入样例 #1

4
6 2
4 4
3 1
10 3

输出样例 #1

8
4
6
11

说明

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.