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>
using namespace std;
const int N = 1e5;
const long long inf = 1ll << 60;
bool p[N + 5];
int np[N + 5], ps;
long long val[N + 5];
void prep() {
  p[0] = p[1] = 1;
  val[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (!p[i]) val[np[++ps] = i] = i - 1;
    for (int j = 1; i * np[j] <= N; j++) {
      p[i * np[j]] = 1;
      if (i % np[j])
        val[i * np[j]] = val[i] * (np[j] - 1);
      else {
        val[i * np[j]] = val[i] * np[j];
        break;
      }
    }
  }
  for (int i = 2; i <= N; i++) val[i] += val[i - 1];
}
int T;
long long f[20][N + 5];
long long s[N + 5];
void solve(int l, int r, int opl, int opr, int k) {
  if (l > r) return;
  int mid = (l + r) >> 1, op;
  if (opr < mid) {
    s[opr + 1] = 0;
    for (int l = opr + 1, r; l <= mid; l = r + 1) {
      r = mid / (mid / l);
      s[opr + 1] += val[mid / l] * (r - l + 1);
    }
  } else
    s[mid] = 1;
  for (int i = min(mid - 1, opr); i >= opl; i--) s[i] = s[i + 1] + val[mid / i];
  f[k][mid] = inf;
  for (int i = opl; i <= min(mid - 1, opr); i++)
    if (f[k - 1][i] + s[i + 1] <= f[k][mid]) {
      f[k][mid] = f[k - 1][i] + s[i + 1];
      op = i;
    }
  solve(l, mid - 1, opl, op, k);
  solve(mid + 1, r, op, opr, k);
}
int main() {
  prep();
  for (int i = 1; i <= N; i++) f[1][i] = 1ll * i * (i + 1) / 2;
  for (int i = 2; i <= 17; i++) {
    for (int j = 1; j < 1 << i; j++) f[i][j] = j;
    solve(1 << i, N, 1, N, i);
  }
  scanf("%d", &T);
  while (T--) {
    int n, k;
    scanf("%d %d", &n, &k);
    if (k > 17)
      printf("%d\n", n);
    else
      printf("%lld\n", f[k][n]);
  }
  return 0;
}
