D. Artistic Partitiontime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputFor 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). InputThe 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). OutputFor each test case, print a single integer — f(n, k).ExampleInput
4
6 2
4 4
3 1
10 3
Output
8
4
6
11
NoteIn 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.
4
6 2
4 4
3 1
10 3

8 4 6 11 
['divide and conquer', 'dp', 'number theory', '*3000']