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;
template <typename T>
void chkmax(T &first, T second) {
  first < second ? first = second : T();
}
template <typename T>
void chkmin(T &first, T second) {
  second < first ? first = second : T();
}
template <typename T>
void readint(T &first) {
  first = 0;
  int f = 1;
  char c;
  for (c = getchar(); !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) first = first * 10 + (c - '0');
  first *= f;
}
const int n = 100000, m = 18;
long long dp[m + 3][n + 3];
int dv[n * 105], ed[n + 3], st[n + 3];
long long now[n + 3], f[n + 3];
int main() {
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; j += i) ++ed[j];
  for (int i = 1; i <= n; ++i) ed[i] += ed[i - 1], st[i] = ed[i];
  for (int i = n; i; --i)
    for (int j = i; j <= n; j += i) dv[st[j]--] = i;
  for (int i = 1; i <= n; ++i) dp[1][i] = 1ll * i * (i + 1) / 2;
  for (int k = 2; k <= m; ++k) {
    memset(now, 0, sizeof(now));
    long long sum = 0;
    for (int r = 1, l = 1; r <= n; ++r) {
      for (int i = ed[r]; i > st[r] && dv[i] >= l; --i) {
        int d = dv[i];
        f[d] = r / d;
        for (int j = ed[r / d]; j > st[r / d] + 1; --j) f[d] -= f[d * dv[j]];
        now[d] += f[d];
        sum += f[d];
      }
      for (; l < r && dp[k - 1][l - 1] >= dp[k - 1][l] - now[l]; ++l)
        sum -= now[l];
      dp[k][r] = dp[k - 1][l - 1] + sum;
    }
  }
  int T;
  readint(T);
  while (T--) {
    int u, k;
    readint(u), readint(k);
    if (k > m)
      printf("%d\n", u);
    else
      printf("%d\n", dp[k][u]);
  }
  return 0;
}
