#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int kMaxN = 1e5 + 7;
constexpr ll mod = 1e9 + 7;
int lp[kMaxN];
vector<int> primes;
ll ans[kMaxN];
ll f[2 * kMaxN];
ll fi[2 * kMaxN];
ll powmod(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b /= 2;
  }
  return res;
}
ll C(ll n, ll k) {
  if (k > n) {
    return 0;
  }
  assert(n < kMaxN);
  return f[n] * fi[k] % mod * fi[n - k] % mod;
}
ll num_ways(ll n, ll k) {
  if (k > n) {
    return 0;
  }
  return C(n - 1, k - 1);
}
ll calc(int n, int f) {
  vector<int> factors;
  int tmp = n;
  while (tmp > 1) {
    if (factors.empty() || factors.back() != lp[tmp]) {
      factors.emplace_back(lp[tmp]);
    }
    tmp /= lp[tmp];
  }
  ll ans = num_ways(n, f);
  for (int i = 1; i < (1 << factors.size()); ++i) {
    ll prod = 1;
    int cx = 0;
    for (int j = 0; j < factors.size(); ++j) {
      if (i & (1 << j)) {
        prod *= factors[j];
        ++cx;
      }
    }
    if (cx & 1) {
      ans = (ans - num_ways(n / prod, f) + mod) % mod;
    } else {
      ans = (ans + num_ways(n / prod, f)) % mod;
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  f[0] = fi[0] = 1;
  for (int i = 1; i < 2 * kMaxN; ++i) {
    f[i] = f[i - 1] * i % mod;
    fi[i] = powmod(f[i], mod - 2);
  }
  for (int i = 2; i < kMaxN; ++i) {
    if (!lp[i]) {
      lp[i] = i;
      primes.emplace_back(i);
    }
    for (int j = 0;
         j < primes.size() && 1LL * i * primes[j] < kMaxN && primes[j] <= lp[i];
         ++j) {
      lp[i * primes[j]] = primes[j];
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int n, f;
    cin >> n >> f;
    cout << calc(n, f) << '\n';
  }
  return 0;
}
