#include <bits/stdc++.h>
using namespace std;
long long exp(long long b, long long e) {
  if (b == 1 || e == 0) return 1;
  if (e == 1) return b % 1000000007;
  if (e == 2) return (b * b) % 1000000007;
  return (((e & 1) == 0)
              ? exp(exp(b, e >> 1), 2) % 1000000007
              : (b * (exp(exp(b, e >> 1), 2) % 1000000007)) % 1000000007);
}
long long gcd(long long a, long long b) {
  return ((b == 0) ? a : gcd(b, a % b));
}
long long sp[100006], fact[100005], invf[100003];
void prime_factors(long long n, vector<int>& ret) {
  int prv = -1;
  while (n != 1) {
    if (sp[n] != prv) {
      ret.push_back(sp[n]);
      prv = sp[n];
    }
    n /= sp[n];
  }
}
int main() {
  sp[1] = 1;
  for (int i = 2; i < 100003; ++i) sp[i] = 2 - 3 * (i & 1);
  for (long long i = 3; i < 100003; i += 2) {
    if (sp[i] != -1) continue;
    sp[i] = i;
    for (long long j = i * i; j < 100003; j += i) {
      if (sp[j] == -1) sp[j] = i;
    }
  }
  fact[0] = invf[0] = 1;
  for (int i = 1; i < 100002; ++i) {
    fact[i] = (fact[i - 1] * i) % 1000000007;
    invf[i] = exp(fact[i], 1000000007 - 2);
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    long long n, f, ans;
    scanf("%lld %lld", &n, &f);
    ans =
        (((fact[n - 1] * invf[n - f]) % 1000000007) * invf[f - 1]) % 1000000007;
    vector<int> pr;
    prime_factors(n, pr);
    long long sz = pr.size();
    for (int i = 1; i < (1 << sz); ++i) {
      int j = i, cnt = 0, k = 0;
      long long num = n;
      while (j != 0) {
        if ((j & 1) == 1) {
          num /= pr[k];
          ++cnt;
        }
        ++k;
        j = (j >> 1);
      }
      if (num < f) continue;
      if ((cnt & 1) == 1)
        ans = (ans -
               (((fact[num - 1] * invf[num - f]) % 1000000007) * invf[f - 1]) %
                   1000000007 +
               1000000007) %
              1000000007;
      else
        ans = (ans +
               (((fact[num - 1] * invf[num - f]) % 1000000007) * invf[f - 1]) %
                   1000000007) %
              1000000007;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
