description: For two positive integers l and r (l ≤ r) let c(l, r) denote the number of integer pairs (i, j) such that l ≤ i ≤ j ≤ r and \operatorname{gcd}(i, j) ≥ 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 ≤ k ≤ n. Let f(n, k) denote the minimum of ∑_{i=1}^{k}{c(x_i+1,x_{i+1})} over all integer sequences 0=x_1 < x_2 < … < x_{k} < x_{k+1}=n.
  
  Help YouKn0wWho find f(n, k). 
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 3 ⋅ 10^5) — the number of test cases.
  
  The first and only line of each test case contains two integers n and k (1 ≤ k ≤ n ≤ 10^5). 
  
  Output
  
  For each test case, print a single integer — f(n, k).
  
  Example
  
  Input
  
  
  4
  6 2
  4 4
  3 1
  10 3
  
  
  Output
  
  
  8
  4
  6
  11
  
  Note
  
  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.
solution: #include <bits/stdc++.h>
  using namespace std;
  long long t, n = 1e5, k, phi[100005], p[100005], prefsum[100005],
               dp[21][100005];
  void solve() {
    cin >> n >> k;
    if (k > 17)
      cout << n << '\n';
    else
      cout << n + dp[k][n] << '\n';
  }
  long long c(long long l, long long r) {
    long long val = 0;
    long long d = l;
    while (d > 0 && r > 0 && r / d > 0) {
      long long cat = r / d;
      long long st = d;
      long long dr = r / cat;
      val += (dr - st + 1) * p[cat];
      d = dr + 1;
    }
    return val;
  }
  void calcdp(int i, int st, int dr, int optl, int optr) {
    if (st > dr) return;
    int mij = (st + dr) / 2;
    bool ok = 0;
    if (mij == 1) ok = 1;
    pair<long long, long long> best = {1e18, -1};
    for (long long k = optl; k <= min(mij, optr); k++)
      best = min(best, {dp[i - 1][k - 1] + c(k, mij), k});
    dp[i][mij] = best.first;
    long long opt = best.second;
    calcdp(i, st, mij - 1, optl, opt);
    calcdp(i, mij + 1, dr, opt, optr);
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 2; i <= 1e5; i++) phi[i] = i;
    for (int i = 2; i <= 1e5; i++) {
      bool prim = (phi[i] == i);
      for (int j = i; j <= 1e5; j += i)
        if (prim) {
          phi[j] /= i;
          phi[j] *= (i - 1);
        }
    }
    for (int i = 1; i <= 1e5; i++) p[i] = p[i - 1] + phi[i];
    for (long long i = 1; i <= n; i++) dp[1][i] = i * (i + 1) / 2 - i;
    for (int i = 2; i <= 17; i++) calcdp(i, 1, n, 1, n);
    cin >> t;
    while (t--) solve();
    return 0;
  }
  