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>
int n = 1e5, k, cnt, p[100010], np[100010], sq[100010];
long long phi[100010], f[20][100010], s1[100010][320], s2[100010][320];
long long c(int l, int r) {
  if (l > r) return 1e16;
  if (r / l <= sq[r])
    return s1[r][r / l] - phi[r / l] * (l - 1 - r / (r / l + 1));
  else
    return s2[r][l];
}
void solve(long long *g, long long *f, int l, int r, int pl, int pr) {
  if (l > r) return;
  int p = 0, mid = (l + r) >> 1;
  f[mid] = 1e16;
  for (int i = pl; i <= pr; i++)
    if (g[i] + c(i + 1, mid) < f[mid]) p = i, f[mid] = g[i] + c(i + 1, mid);
  solve(g, f, l, mid - 1, pl, p), solve(g, f, mid + 1, r, p, pr);
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
  phi[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!np[i]) p[++cnt] = i, phi[i] = i - 1;
    for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
      np[i * p[j]] = 1;
      if (i % p[j] == 0) {
        phi[i * p[j]] = phi[i] * p[j];
        break;
      }
      phi[i * p[j]] = phi[i] * phi[p[j]];
    }
  }
  for (int i = 1; i <= n; i++) phi[i] += phi[i - 1];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j * j <= i; j++) {
      s1[i][j] = s1[i][j - 1] + phi[j] * (i / j - i / (j + 1));
      sq[i] = j;
    }
    s2[i][i / (sq[i] + 1) + 1] = s1[i][sq[i]];
    for (int j = i / (sq[i] + 1); j; j--) {
      s2[i][j] = s2[i][j + 1] + phi[i / j];
    }
  }
  for (int i = 1; i <= n; i++) f[1][i] = c(1, i);
  for (int i = 2; i <= 17; i++) solve(f[i - 1], f[i], 1, n, 1, n);
  int T;
  std::cin >> T;
  while (T--) {
    scanf("%d%d", &n, &k);
    if (k > 17)
      printf("%d\n", n);
    else
      printf("%lld\n", f[k][n]);
  }
  return 0;
}
