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 maxn = 1e5 + 50, maxm = 330;
const long long inf = 1e18;
int T, n, k, vis[maxn], p[maxn], sq[maxn], phi[maxn];
long long sp[maxn], s1[maxn][maxm], s2[maxn][maxm], f[maxn][20];
int read() {
  int x = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline long long calc(int l, int r) {
  int t = r / l;
  if (t <= sq[r])
    return s2[r][t - 1] + 1ll * (r / t - l + 1) * sp[t];
  else
    return s1[r][l];
}
void init(int n) {
  phi[1] = 1;
  for (int i = 2, tot = 0; i <= n; i++) {
    if (!vis[i]) p[++tot] = i, phi[i] = i - 1;
    for (int j = 1, t; j <= tot && (t = i * p[j]) <= n; j++) {
      vis[t] = 1;
      if (i % p[j] == 0) {
        phi[t] = phi[i] * p[j];
        break;
      } else
        phi[t] = phi[i] * phi[p[j]];
    }
  }
  for (int i = 1; i <= n; i++) sp[i] = sp[i - 1] + phi[i];
  for (int i = 1; i <= n; i++) {
    sq[i] = 0;
    while ((sq[i] + 1) * (sq[i] + 1) <= i) sq[i]++;
    int l = 1, r;
    while (l <= i) {
      r = i / (i / l);
      if (r <= sq[i])
        s1[i][r] = 1ll * (r - l + 1) * sp[i / l];
      else
        s2[i][i / r] = 1ll * (r - l + 1) * sp[i / l];
      l = r + 1;
    }
    for (int j = 1; j <= sq[i]; j++) s2[i][j] += s2[i][j - 1];
    s1[i][sq[i]] += s2[i][sq[i]];
    for (int j = sq[i] - 1; j >= 1; j--) s1[i][j] += s1[i][j + 1];
  }
  for (int i = 1; i <= n; i++) f[i][0] = inf;
  f[0][0] = 0;
  for (int j = 1; j <= 16; j++) {
    int p = 0;
    for (int i = 1; i <= n; i++) {
      while (p + 1 < i &&
             f[p + 1][j - 1] + calc(p + 2, i) <= f[p][j - 1] + calc(p + 1, i))
        p++;
      f[i][j] = f[p][j - 1] + calc(p + 1, i);
    }
  }
}
int main() {
  init(1e5);
  int cnt = 0;
  T = read();
  while (T--) {
    n = read(), k = read();
    cnt++;
    if (cnt == 200072) cout << n << ' ' << k << endl;
    if (k >= 17)
      printf("%d\n", n);
    else
      printf("%lld\n", f[n][k]);
  }
  return 0;
}
