#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline int popcount(T t) {
  if (std::numeric_limits<T>::digits <=
      std::numeric_limits<unsigned int>::digits) {
    return __builtin_popcount(t);
  } else {
    return __builtin_popcountll(t);
  }
}
const long double EPS = 1e-8;
const long double PI = acosl(0.0) * 2;
const long long MOD = 1000000007;
const int NMAX = 100400;
long long fact[NMAX];
long long pow(long long a, long long n) {
  long long ret = 1;
  while (n > 0) {
    if (n & 1) ret = ret * a % MOD;
    a = a * a % MOD;
    n >>= 1;
  }
  return ret;
}
long long inv(long long a) { return pow(a, MOD - 2); }
long long c(long long n, long long k) {
  return fact[n] * inv(fact[k]) % MOD * inv(fact[n - k]) % MOD;
}
vector<int> getPrimes(int n) {
  vector<int> ret;
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      ret.push_back(i);
    }
  }
  if (n > 1) ret.push_back(n);
  return ret;
}
long long calc(long long n, long long f) {
  if (n < f) return 0;
  n -= f;
  return c(n + f - 1, f - 1);
}
void solve() {
  fact[0] = 1;
  for (int i = 1; i <= int(NMAX - 1); ++i) fact[i] = fact[i - 1] * i % MOD;
  int q;
  cin >> q;
  for (int it = 0; it < int(q); ++it) {
    int n, f;
    cin >> n >> f;
    long long ans = 0;
    vector<int> primes = getPrimes(n);
    int m = primes.size();
    for (int mask = 0; mask < int(1 << m); ++mask) {
      int sign = (popcount(mask) % 2 == 0) ? 1 : -1;
      long long div = 1;
      for (int i = 0; i < int(m); ++i)
        if (mask & (1 << i)) div *= primes[i];
      assert(n % div == 0);
      ans += sign * calc(n / div, f);
      ans = (ans + MOD) % MOD;
    }
    cout << ans << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  solve();
  return 0;
}
