#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet {
long long I() {
  long long x = 0;
  char c = getchar();
  long long f = 1;
  while (c < '0' or c > '9') f = (c == '-') ? -1 : 1, c = getchar();
  while (c >= '0' and c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return (x = (f == 1) ? x : -x);
}
void Rd(long long cnt, ...) {
  va_list args;
  va_start(args, cnt);
  for (long long i = 1; i <= cnt; ++i) {
    long long* x = va_arg(args, long long*);
    (*x) = I();
  }
  va_end(args);
}
bool notp[155555];
long long primes[155555];
long long mu[155555];
long long fac[155555], ifac[155555], inv[155555];
void Init() {
  long long n = 1e5;
  notp[1] = 1;
  mu[1] = 1;
  long long& cnt = primes[0];
  for (long long i = 2; i <= n; ++i) {
    if (!notp[i]) primes[++cnt] = i, mu[i] = -1;
    for (long long j = 1; j <= cnt and i * primes[j] <= n; ++j) {
      long long u = primes[j];
      notp[i * u] = 1;
      if (i % u) {
        mu[i * u] = -mu[i];
      } else {
        mu[i * u] = 0;
        break;
      }
    }
  }
  fac[0] = 1;
  for (long long i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % 1000000007;
  inv[1] = 1;
  for (long long i = 2; i <= n; ++i)
    inv[i] = (1000000007 - 1000000007 / i) * inv[1000000007 % i] % 1000000007;
  ifac[0] = 1;
  for (long long i = 1; i <= n; ++i)
    ifac[i] = ifac[i - 1] * inv[i] % 1000000007;
}
long long n, k;
void Input() { Rd(2, &n, &k); }
long long C(long long n, long long m) {
  return m > n ? 0 : fac[n] * ifac[m] % 1000000007 * ifac[n - m] % 1000000007;
}
long long calc1(long long n, long long k) { return C(n - 1, k - 1); }
void Soviet() {
  long long ans = 0;
  for (long long i = 1; i * i <= n; ++i)
    if (n % i == 0) {
      ans += mu[i] * calc1(n / i, k), ans %= 1000000007;
      if (i != n / i) ans += mu[n / i] * calc1(i, k), ans %= 1000000007;
    }
  printf("%lld\n", (ans % 1000000007 + 1000000007) % 1000000007);
}
void IsMyWife() {
  Init();
  long long t = I();
  for (long long i = 1; i <= t; ++i) {
    Input();
    Soviet();
  }
}
}  // namespace Flandre_Scarlet
int main() {
  Flandre_Scarlet::IsMyWife();
  getchar();
  getchar();
  return 0;
}
