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.
#include <bits/stdc++.h>
const int N = 100001;
int t, n, k, p[N], pr[N], cp;
long long dp[18][N], P[N];
bool v[N];
long long c(int l, int r) {
  long long s = 0;
  int k;
  for (int i = l, j = r / i; i <= r; i = k + 1, j = r / i) {
    k = r / j, s += P[j] * (k - i + 1);
  }
  return s;
}
void solve(int l, int r, int dl, int dr, int k) {
  if (l > r) return;
  int m = (l + r) >> 1, dm = -1;
  long long dmin = -1;
  for (int i = dl; i <= std::min(dr, m - 1); ++i) {
    long long dtmp = dp[k - 1][i] + c(i + 1, m);
    if (dmin == -1 || dtmp < dmin) {
      dmin = dtmp;
      dm = i;
    }
  }
  assert(dmin != -1);
  dp[k][m] = dmin;
  solve(l, m - 1, dl, dm, k), solve(m + 1, r, dm, dr, k);
}
int main() {
  scanf("%d", &t);
  p[1] = P[1] = 1;
  for (int i = 2; i <= 10; ++i) {
    if (!v[i]) pr[++cp] = i, p[i] = i - 1;
    for (int j = 1; j <= cp && i * pr[j] <= 10; ++j) {
      v[i * pr[j]] = 1, p[i * pr[j]] = p[i] * (pr[j] - 1);
      if (i % pr[j] == 0) {
        p[i * pr[j]] += p[i];
        break;
      }
    }
    P[i] = P[i - 1] + p[i];
  }
  for (int i = 1; i <= 10; ++i) dp[1][i] = 1ll * i * (i + 1) / 2ll;
  for (int k = 2; k <= 17; ++k) solve(1, 10, 0, 10, k);
  while (t--) {
    scanf("%d%d", &n, &k);
    if (k >= 18 || k > log(n) / log(2))
      printf("%d\n", n);
    else
      printf("%lld\n", dp[k][n]);
  }
  return 0;
}
