#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int lim = 1e5;
int t, x, n, fac[100005], inv[100005];
long long res;
int read() {
  int x = 0, fl = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') fl = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * fl;
}
int qpow(int base, int pw) {
  int s = 1;
  while (pw) {
    if (pw & 1) s = 1ll * s * base % mod;
    base = 1ll * base * base % mod;
    pw >>= 1;
  }
  return s;
}
int C(int x, int y) {
  if (x < y) return 0;
  return 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;
}
int mu(int x) {
  int p = 1;
  for (int i = 2; i * i <= x; i++) {
    if (x % i) continue;
    x /= i;
    p = -p;
    if (x % i == 0) return 0;
  }
  if (x > 1) p = -p;
  return p;
}
int main() {
  fac[0] = 1;
  for (int i = 1; i <= lim; i++)
    fac[i] = 1ll * fac[i - 1] * (long long)(i) % mod;
  inv[lim] = qpow(fac[lim], mod - 2);
  for (int i = lim - 1; i >= 0; i--)
    inv[i] = 1ll * inv[i + 1] * (long long)(i + 1) % mod;
  t = read();
  while (t--) {
    x = read(), n = read(), res = 0;
    for (int i = 1; i * i <= x; i++) {
      if (x % i) continue;
      res = (res + 1ll * mu(i) * C(x / i - 1, n - 1) % mod + mod) % mod;
      if (i * i != x)
        res = (res + 1ll * mu(x / i) * C(i - 1, n - 1) % mod + mod) % mod;
    }
    printf("%lld\n", res);
  }
  return 0;
}
