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;
inline int read() {
  int x = 0, sgn = 0;
  char s = getchar();
  while (!isdigit(s)) sgn |= s == '-', s = getchar();
  while (isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(long long x) {
  if (x < 0)
    putchar('-'), print(-x);
  else {
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
  }
}
template <class T>
void cmin(T &a, T b) {
  a = a < b ? a : b;
}
template <class T>
void cmax(T &a, T b) {
  a = a > b ? a : b;
}
const int N = 1e5 + 5;
const int K = 18;
long long T, n, k, f[K][N];
long long cst(long long l, long long r) {
  return (r / l) * (r / l - 1) / 2 + r - l + 1;
}
void solve(int l, int r, int pl, int pr, long long *f, long long *g) {
  int m = l + r >> 1, lim = min(pr, m - 1), p = pl;
  g[m] = f[pl] + cst(pl + 1, m);
  for (int i = pl + 1; i <= lim; i++)
    if (f[i] + cst(i + 1, m) < g[m]) g[m] = f[i] + cst(i + 1, m), p = i;
  if (l < m) solve(l, m - 1, max(0, pl - 10), min(m - 2, p + 10), f, g);
  if (m < r) solve(m + 1, r, max(0, p - 10), min(r - 1, pr + 10), f, g);
}
int main() {
  memset(f[0], 0x3f, sizeof(f[0][0]) * (N)), f[0][0] = 0, cin >> T;
  for (int i = 1; i < K; i++) solve(1, N - 1, 0, N - 2, f[i - 1], f[i]);
  while (T--) {
    cin >> n >> k;
    if (k >= K)
      cout << n << endl;
    else if (n <= (1 << k) - 1)
      cout << n << endl;
    else
      cout << f[k][n] << endl;
  }
  return 0;
}
