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 long long maxl = 300005, maxg = 22, maxq = 300005;
  long long read() {
    long long s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
      if (ch == '-') w = -w;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      s = (s << 1) + (s << 3) + (ch ^ '0');
      ch = getchar();
    }
    return s * w;
  }
  long long t, n, pos;
  long long prime[maxl], phi[maxl], pre[maxl], f[maxg][maxl];
  struct Querylist {
    long long query_n, query_k;
  } lis[maxq];
  namespace Math {
  bool is_p[maxl];
  void get_phi() {
    phi[1] = 1;
    for (long long i = 2; i <= n; i++) {
      if (!is_p[i]) prime[++pos] = i, phi[i] = i - 1;
      for (long long j = 1; j <= pos; j++) {
        long long p = prime[j];
        if (i * p > n) break;
        is_p[i * p] = 1;
        if (i % p)
          phi[i * p] = phi[i] * phi[p];
        else {
          phi[i * p] = phi[i] * p;
          break;
        }
      }
    }
  }
  void get_pre() {
    for (long long i = 1; i <= n; i++) pre[i] = pre[i - 1] + phi[i];
    for (long long i = 1; i <= n; i++) pre[i] = 2 * pre[i] - 1;
  }
  long long calc(long long x, long long l, long long r) {
    r = min(r, x);
    if (l > r || l > x) return 0;
    long long tot = 0;
    for (long long i = l; i <= r; i++) {
      long long j = min(x / (x / i), r);
      tot += (pre[x / i] - 1) * (j - i + 1);
      i = j;
    }
    return tot;
  }
  void work() { get_phi(), get_pre(); }
  }  // namespace Math
  namespace ducati {
  void get_all_in() {
    t = read();
    for (long long i = 1; i <= t; i++) {
      lis[i].query_n = read(), lis[i].query_k = read();
      n = max(n, lis[i].query_n);
    }
  }
  void DP(long long id, long long l, long long r, long long L, long long R) {
    if (l > r) return;
    long long mid = (l + r) >> 1, sumv = Math::calc(mid, min(R, mid) + 1, mid),
              pos = 0;
    for (long long i = min(R, mid); i >= L; i--) {
      sumv += (pre[mid / i] - 1);
      long long val = f[id - 1][i - 1] + sumv;
      if (val < f[id][mid]) f[id][mid] = val, pos = i;
    }
    DP(id, l, mid - 1, L, pos), DP(id, mid + 1, r, pos, R);
  }
  void init() {
    for (long long i = 0; i <= log2(n); i++) {
      for (long long j = 1; j <= n; j++) f[i][j] = 200000000000000007;
    }
  }
  void work() {
    for (long long i = 1; i <= log2(n); i++) DP(i, 1, n, 1, n);
    for (long long i = 1; i <= t; i++) {
      long long N = lis[i].query_n, K = lis[i].query_k, ans = lis[i].query_n;
      if (K <= log2(N)) ans = (f[K][N] / 2) + N;
      printf("%lld\n", ans);
    }
  }
  void solve() {
    get_all_in();
    Math::work();
    init(), work();
  }
  }  // namespace ducati
  signed main() {
    ducati::solve();
    return 0;
  }
  