#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
const int ALL = 1e5;
int fac[MAXN], ifac[MAXN];
int is[MAXN], mu[MAXN], p[MAXN], t;
inline int read() {
  int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline int qpow(int x, int y = MOD - 2) {
  long long r = 1, k = x;
  while (y) {
    if (y & 1) r *= k, r %= MOD;
    k *= k, k %= MOD, y >>= 1;
  }
  return r;
}
inline void prepare() {
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= ALL; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
  ifac[ALL] = qpow(fac[ALL]);
  for (int i = ALL - 1; ~i; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % MOD;
}
inline int C(int x, int y) {
  if (x < y || x < 0 || y < 0) return 0;
  return 1ll * fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}
inline void init() {
  is[1] = mu[1] = 1;
  for (int i = 2; i <= ALL; i++) {
    if (!is[i]) p[++t] = i, mu[i] = -1;
    for (int j = 1; j <= t && i * p[j] <= ALL; j++) {
      is[i * p[j]] = 1, mu[i * p[j]] = -mu[i];
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
    }
  }
}
int main() {
  int t = read();
  prepare(), init();
  while (t--) {
    long long ans = 0;
    int n = read(), m = read();
    for (int i = 1; i * i <= n; i++) {
      if (n % i) continue;
      ans += mu[i] * C(n / i - 1, m - 1);
      if (i * i != n) ans += mu[n / i] * C(i - 1, m - 1);
    }
    printf("%lld\n", ((ans % MOD) + MOD) % MOD);
  }
  return 0;
}
