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, LOG = 18;
  inline int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
      if (ch == '-') f = -1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
    return s * f;
  }
  const long long inf = 1e18;
  int prime[N], pcnt;
  long long phi[N];
  bool vis[N];
  void init(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
      if (!vis[i]) {
        prime[++pcnt] = i;
        phi[i] = i - 1;
      }
      for (int j = 1; j <= pcnt && prime[j] * i <= n; ++j) {
        vis[prime[j] * i] = 1;
        if (i % prime[j] == 0) {
          phi[i * prime[j]] = phi[i] * prime[j];
          break;
        }
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);
      }
    }
    for (int i = 1; i <= n; ++i) phi[i] += phi[i - 1];
  }
  inline long long calc(int l, int r) {
    long long ret = 0;
    for (int i; l <= r; l = i + 1) {
      i = min(r / (r / l), r);
      ret += 1ll * phi[r / l] * (i - l + 1);
    }
    return ret;
  }
  inline long long c(int l, int r) { return phi[r / l]; }
  int T, n, k;
  long long f[N][LOG], g[N][LOG];
  void solve(int l, int r, int L, int R) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    long long sum = calc(R + 1, mid);
    int pos = 0;
    long long mn = inf;
    for (int i = min(mid, R); i >= L; --i) {
      sum += phi[mid / i];
      if (sum + f[i - 1][k - 1] <= mn) {
        mn = sum + f[i - 1][k - 1];
        pos = i;
      }
    }
    f[mid][k] = mn;
    solve(l, mid - 1, L, pos);
    solve(mid + 1, r, pos, R);
  }
  int main() {
    n = 100000;
    init(n);
    for (int i = 1; i <= n; ++i) g[i][1] = f[i][1] = (1ll * i * (i + 1)) >> 1;
    for (k = 2; k <= 17; ++k) solve(1, n, 1, n);
    T = read();
    while (T--) {
      n = read();
      k = read();
      if (k >= 20 || n < (1 << k)) {
        printf("%d\n", n);
        continue;
      }
      printf("%lld\n", f[n][k]);
    }
    return 0;
  }
  