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;
  const int N = 1e5 + 5;
  const int64_t inf = 1e18;
  int phi[N];
  int64_t p[N], dp[18][N];
  inline void __calc__() {
    for (int i = 1; i < N; i++) phi[i] = i;
    for (int i = 2; i < N; i++)
      if (phi[i] == i) {
        for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
      }
    for (int i = 1; i < N; i++) p[i] = p[i - 1] + phi[i];
  }
  inline bool chkmin(int64_t &a, int64_t b) { return a > b ? a = b, 1 : 0; }
  inline int64_t cost(int l, int r) {
    if (l > r) return inf;
    int64_t res = 0;
    for (int i = l, j; i <= r; i = j + 1) {
      j = r / (r / i);
      if (j > r) j = r;
      res += (j - i + 1) * p[r / i];
    }
    return res;
  }
  void solve(int k, int l, int r, int opt_l, int opt_r) {
    if (l > r) return;
    int m = l + r >> 1, opt_m = opt_l;
    int64_t cst = cost(opt_m, m);
    for (int i = opt_l; i <= opt_r && i <= m; i++) {
      if (chkmin(dp[k][m], dp[k - 1][i - 1] + cst)) opt_m = i;
      cst -= p[m / i];
    }
    solve(k, l, m - 1, opt_l, opt_m);
    solve(k, m + 1, r, opt_m, opt_r);
  }
  signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    __calc__();
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= N - 5; i++) dp[1][i] = 1ll * i * (i + 1) / 2;
    for (int i = 2; i < 18; i++) solve(i, 1, N - 5, 1, N - 5);
    int q;
    cin >> q;
    for (int n, k; q--;) {
      cin >> n >> k;
      cout << (k > 18 || (1 << k) > n ? n : dp[k][n]) << '\n';
    }
  }
  