#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int64_t inf = 1e18;
int phi[N];
int64_t p[N], dp[18][N];
inline void __calc__() {
  for (int i = 1; i < N; i++) phi[i] = i;
  for (int i = 2; i < N; i++)
    if (phi[i] == i) {
      for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    }
  for (int i = 1; i < N; i++) p[i] = p[i - 1] + phi[i];
}
inline bool chkmin(int64_t &a, int64_t b) { return a > b ? a = b, 1 : 0; }
inline int64_t cost(int l, int r) {
  if (l > r) return inf;
  int64_t res = 0;
  for (int i = l, j; i <= r; i = j + 1) {
    j = r / (r / i);
    if (j > r) j = r;
    res += (j - i + 1) * p[r / i];
  }
  return res;
}
void solve(int k, int l, int r, int opt_l, int opt_r) {
  if (l > r) return;
  int m = l + r >> 1, opt_m = opt_l;
  int64_t cst = cost(opt_m, m);
  for (int i = opt_l; i <= opt_r && i <= m; i++) {
    if (chkmin(dp[k][m], dp[k - 1][i - 1] + cst)) opt_m = i;
    cst -= p[m / i];
  }
  solve(k, l, m - 1, opt_l, opt_m);
  solve(k, m + 1, r, opt_m, opt_r);
}
signed main() {
  cin.tie(0), cout.tie(0)->sync_with_stdio(0);
  __calc__();
  memset(dp, 0x3f, sizeof dp);
  for (int i = 1; i <= N - 5; i++) dp[1][i] = 1ll * i * (i + 1) / 2;
  for (int i = 2; i < 18; i++) solve(i, 1, N - 5, 1, N - 5);
  int q;
  cin >> q;
  for (int n, k; q--;) {
    cin >> n >> k;
    cout << (k > 18 || (1 << k) > n ? n : dp[k][n]) << '\n';
  }
}

### Prompt

Please formulate a Cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int64_t inf = 1e18;
int phi[N];
int64_t p[N], dp[18][N];
inline void __calc__() {
  for (int i = 1; i < N; i++) phi[i] = i;
  for (int i = 2; i < N; i++)
    if (phi[i] == i) {
      for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    }
  for (int i = 1; i < N; i++) p[i] = p[i - 1] + phi[i];
}
inline bool chkmin(int64_t &a, int64_t b) { return a > b ? a = b, 1 : 0; }
inline int64_t cost(int l, int r) {
  if (l > r) return inf;
  int64_t res = 0;
  for (int i = l, j; i <= r; i = j + 1) {
    j = r / (r / i);
    if (j > r) j = r;
    res += (j - i + 1) * p[r / i];
  }
  return res;
}
void solve(int k, int l, int r, int opt_l, int opt_r) {
  if (l > r) return;
  int m = l + r >> 1, opt_m = opt_l;
  int64_t cst = cost(opt_m, m);
  for (int i = opt_l; i <= opt_r && i <= m; i++) {
    if (chkmin(dp[k][m], dp[k - 1][i - 1] + cst)) opt_m = i;
    cst -= p[m / i];
  }
  solve(k, l, m - 1, opt_l, opt_m);
  solve(k, m + 1, r, opt_m, opt_r);
}
signed main() {
  cin.tie(0), cout.tie(0)->sync_with_stdio(0);
  __calc__();
  memset(dp, 0x3f, sizeof dp);
  for (int i = 1; i <= N - 5; i++) dp[1][i] = 1ll * i * (i + 1) / 2;
  for (int i = 2; i < 18; i++) solve(i, 1, N - 5, 1, N - 5);
  int q;
  cin >> q;
  for (int n, k; q--;) {
    cin >> n >> k;
    cout << (k > 18 || (1 << k) > n ? n : dp[k][n]) << '\n';
  }
}

```