#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& a) {
  return os << "(" << a.first << "," << a.second << ")";
}
template <class T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cout << (*i) << " ";
  cout << endl;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
int nextInt() {
  int x;
  scanf("%d", &x);
  return x;
}
const long long MOD = 1000000007;
const int SZ = 312345;
long long inv[SZ];
long long fact[SZ];
long long fact_inv[SZ];
long long choose(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return fact[n] * fact_inv[n - r] % MOD * fact_inv[r] % MOD;
}
vector<int> primes;
bool isPrime[SZ];
void make_primes() {
  if (primes.size() > 0) return;
  memset(isPrime, true, sizeof(isPrime));
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; i * i < SZ; i++)
    if (isPrime[i])
      for (int j = i * i; j < SZ; j += i) isPrime[j] = false;
  for (int i = 0, _n = (int)(SZ); i < _n; ++i)
    if (isPrime[i]) primes.push_back(i);
}
const int MAX_N = SZ;
int mobius[MAX_N];
void make_mobius() {
  for (int i = 0; i < MAX_N; i++) mobius[i] = 1;
  for (int i = 2; i < MAX_N; i++)
    if (isPrime[i])
      for (int j = i; j < MAX_N; j += i)
        if (j / i % i == 0)
          mobius[j] = 0;
        else
          mobius[j] *= -1;
}
long long H(int n, int m) { return choose(n + m - 1, n); }
long long p(int n, int f) {
  if (n < f) return 0;
  return H(n - f, f);
}
int main2() {
  int q = nextInt();
  for (; q--;) {
    int n = nextInt();
    int f = nextInt();
    long long ans = 0;
    for (int d = 1; d * d <= n; d++) {
      if (n % d == 0) {
        int x = d;
        if (mobius[x]) {
          ans += mobius[x] * p(n / x, f);
          ans %= MOD;
        }
        if (d * d != n) {
          int x = n / d;
          if (mobius[x]) {
            ans += mobius[x] * p(n / x, f);
            ans %= MOD;
          }
        }
      }
    }
    ans = ((ans % MOD) + MOD) % MOD;
    printf("%lld\n", ans);
  }
  return 0;
}
int main() {
  make_primes();
  make_mobius();
  inv[1] = 1;
  for (int i = 2; i < SZ; i++)
    inv[i] = inv[(int)(MOD % i)] * (MOD - MOD / i) % MOD;
  fact[0] = 1;
  for (int i = 1; i < SZ; i++) fact[i] = fact[i - 1] * i % MOD;
  fact_inv[0] = 1;
  for (int i = 1; i < SZ; i++) fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
  for (; !cin.eof(); cin >> ws) main2();
  return 0;
}
