D. Artistic Partition
divide and conquer; dp; number theory
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)\).
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)\).
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.