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>
  #pragma GCC optimize(3)
  using namespace std;
  using ll = long long;
  template <class T>
  void read(T &x) {
    char ch;
    x = 0;
    int f = 1;
    while (isspace(ch = getchar_unlocked()))
      ;
    if (ch == '-') ch = getchar_unlocked(), f = -1;
    do x = x * 10 + (ch - '0');
    while (isdigit(ch = getchar_unlocked()));
    x *= f;
  }
  template <class T, class... A>
  void read(T &x, A &...args) {
    read(x);
    read(args...);
  }
  const int B = 18;
  const int N = 100005;
  const ll INF = 0x3f3f3f3f3f3f3f3f;
  int phi[N], p[N], pc = 0;
  bool np[N];
  void sieve(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
      if (!np[i]) p[++pc] = i, phi[i] = i - 1;
      for (int j = 1; j <= pc && i * p[j] <= n; ++j) {
        np[i * p[j]] = true;
        if (i % p[j] == 0) {
          phi[i * p[j]] = phi[i] * p[j];
          break;
        }
        phi[i * p[j]] = phi[i] * (p[j] - 1);
      }
    }
  }
  struct node {
    ll mn[B], tag;
  } t[N * 4];
  void up(int x) {
    for (int i = 0; i < B; ++i)
      t[x].mn[i] = min(t[x << 1].mn[i], t[x << 1 | 1].mn[i]) + t[x].tag;
  }
  void tag(int x, int val) {
    for (int i = 0; i < B; ++i) t[x].mn[i] += val;
    t[x].tag += val;
  }
  void modify(int x, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
      tag(x, v);
      return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) modify(x << 1, l, mid, ql, qr, v);
    if (qr > mid) modify(x << 1 | 1, mid + 1, r, ql, qr, v);
    up(x);
  }
  void assign(int x, int l, int r, int p, const ll *v, int tag = 0) {
    if (l == r) {
      for (int i = 0; i < B; ++i) t[x].mn[i] = v[i] - tag;
      return;
    }
    int mid = (l + r) >> 1;
    tag += t[x].tag;
    p <= mid ? assign(x << 1, l, mid, p, v, tag)
             : assign(x << 1 | 1, mid + 1, r, p, v, tag);
    up(x);
  }
  void build(int x, int l, int r) {
    memset(t[x].mn, 0x3f, sizeof(t[x].mn));
    if (l == 0) t[x].mn[0] = 0;
    t[x].tag = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
  }
  ll dp[N][B];
  vector<int> di[N];
  void prework(int n) {
    sieve(n);
    for (int i = 1; i <= n; ++i)
      for (int j = i; j <= n; j += i) di[j].push_back(i);
    build(1, 0, n);
    for (int i = 1; i <= n; ++i) {
      for (int d : di[i]) modify(1, 0, n, 0, d - 1, phi[i / d]);
      dp[i][0] = INF;
      for (int j = 0; j < B - 1; ++j) dp[i][j + 1] = t[1].mn[j];
      assign(1, 0, n, i, dp[i]);
    }
  }
  int main() {
    int qc;
    read(qc);
    prework(100000);
    while (qc--) {
      int n, k;
      read(n, k);
      if (k >= B)
        printf("%d\n", n);
      else
        printf("%lld\n", dp[n][k]);
    }
    return 0;
  }
  