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>
  template <class T>
  inline T read() {
    T r = 0, f = 0;
    char c;
    while (!isdigit(c = getchar())) f |= (c == '-');
    while (isdigit(c)) r = (r << 1) + (r << 3) + (c ^ 48), c = getchar();
    return f ? -r : r;
  }
  template <class T>
  inline T abs(T a) {
    return a < 0 ? -a : a;
  }
  template <class T>
  inline T min(T a, T b) {
    return a < b ? a : b;
  }
  template <class T>
  inline T max(T a, T b) {
    return a > b ? a : b;
  }
  inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
  inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
  inline long long qpow(long long a, int b) {
    long long ans = 1;
    for (; b; b >>= 1) {
      if (b & 1) (ans *= a) %= 998244353;
      (a *= a) %= 998244353;
    }
    return ans;
  }
  struct Z {
    int x;
    inline int val() const { return x; }
    inline int inv() const { return qpow(x, 998244353 - 2); }
    Z(int x = 0) : x(x) {}
    Z operator-() const {
      return Z((998244353 - x >= 998244353 ? 998244353 - x - 998244353
                                           : 998244353 - x));
    }
    Z &operator+=(const Z &z) {
      x = (x + z.x >= 998244353 ? x + z.x - 998244353 : x + z.x);
      return *this;
    }
    Z &operator-=(const Z &z) {
      x = (x - z.x < 0 ? x - z.x + 998244353 : x - z.x);
      return *this;
    }
    Z &operator*=(const Z &z) {
      x = 1ll * x * z.x % 998244353;
      return *this;
    }
    Z &operator/=(const Z &z) {
      x = 1ll * x * z.inv() % 998244353;
      return *this;
    }
    Z operator+(const Z &z) const {
      return Z((x + z.x >= 998244353 ? x + z.x - 998244353 : x + z.x));
    }
    Z operator-(const Z &z) const {
      return Z((x - z.x < 0 ? x - z.x + 998244353 : x - z.x));
    }
    Z operator*(const Z &z) const { return Z(1ll * x * z.x % 998244353); }
    Z operator/(const Z &z) const { return Z(1ll * x * z.inv() % 998244353); }
  };
  template <int T>
  struct Hash {
    struct E {
      int v, w, nxt;
      E() {}
      E(int v, int w, int nxt) : v(v), w(w), nxt(nxt) {}
    } e[T + 100];
    int s_e, head[T + 100];
    std::vector<int> d;
    inline void a_e(int u, int v, int w) {
      e[++s_e] = E(v, w, head[u]);
      head[u] = s_e;
    }
    inline int H(int x) { return (1ll * x * x + (x & T) + (x ^ T)) % T + 1; }
    int &operator[](const int x) {
      int u = H(x);
      for (int i = head[u]; i; i = e[i].nxt)
        if (e[i].v == x) return e[i].w;
      a_e(u, x, 0);
      d.push_back(x);
      return e[head[u]].w;
    }
    inline void clear() {
      s_e = 0;
      for (auto u : d) head[H(u)] = 0;
      d.clear();
    }
  };
  long long sum[101101], f[22][101101];
  inline void init(int N) {
    for (int i = 1; i <= N; i++) sum[i] = i;
    for (int i = 2; i <= N; i++) {
      if (sum[i] ^ i) continue;
      for (int j = i; j <= N; j += i) sum[j] -= sum[j] / i;
    }
    for (int i = 2; i <= N; i++) sum[i] += sum[i - 1];
  }
  inline long long C(int L, int R) {
    long long ans = 0;
    for (int l = L, r; l <= R; l = r + 1)
      r = R / (R / l), ans += sum[R / l] * (r - l + 1);
    return ans;
  }
  int k;
  void solve(int l, int r, int L, int R) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    int Mid = min(mid - 1, R);
    long long c = C(Mid + 1, mid);
    long long val = 1e18;
    for (int i = Mid; i >= L; i--) {
      long long cost = f[k - 1][i] + c;
      if (cost < val) val = cost, Mid = i;
      c += sum[mid / i];
    }
    f[k][mid] = val;
    solve(l, mid - 1, L, Mid);
    solve(mid + 1, r, Mid, R);
  }
  const int N = 1e5;
  int main() {
    init(N);
    for (int i = 1; i <= N; i++) f[1][i] = 1ll * i * (i + 1) / 2;
    for (k = 2; k <= 16; k++) solve(k, N, k - 1, N - 1);
    int t = read<int>();
    while (t--) {
      int n = read<int>();
      int k = read<int>();
      if (k > 16)
        printf("%d\n", n);
      else
        printf("%lld\n", f[k][n]);
    }
    return 0;
  }
  