#include <bits/stdc++.h>
using namespace std;
const long long sz = 1e5 + 10, mod = 1e9 + 7;
vector<long long> dv[sz];
long long dp[sz], fact[sz], inv[sz], totalWay[sz];
unordered_map<int, int> ret[sz];
long long fastPow(long long x, long long n, long long MOD) {
  long long ret = 1;
  while (n) {
    if (n & 1) ret = (ret * x) % MOD;
    x = (x * x) % MOD;
    n >>= 1;
  }
  return ret % MOD;
}
inline long long starsBars(long long n, long long k) {
  n--, k--;
  long long den = (inv[k] * inv[n - k]) % mod;
  return (fact[n] * den) % mod;
}
long long solve(long long n, long long f) {
  if (n < f) return 0;
  if (dp[n] != -1) return dp[n];
  long long way = starsBars(n, f);
  for (long long &g : dv[n]) {
    way -= solve(n / g, f);
    if (way < 0) way += mod;
  }
  return dp[n] = way;
}
int main() {
  for (long long i = 2; i < sz; i++)
    for (long long j = i + i; j < sz; j += i) dv[j].push_back(i);
  fact[0] = 1;
  for (long long i = 1; i <= sz - 1; ++i) fact[i] = (fact[i - 1] * i) % mod;
  inv[sz - 1] = fastPow(fact[sz - 1], mod - 2, mod);
  for (long long i = (sz - 1 - 1); i >= 0; --i)
    inv[i] = (inv[i + 1] * (i + 1)) % mod;
  long long q;
  cin >> q;
  while (q--) {
    long long n, f;
    scanf("%lld", &n), scanf("%lld", &f);
    if (f == 1) {
      if (n == 1)
        printf("1\n");
      else
        printf("0\n");
      continue;
    }
    if (ret[n].find(f) != ret[n].end()) {
      printf("%d\n", ret[n][f]);
      continue;
    }
    for (long long &d : dv[n]) dp[d] = -1;
    dp[n] = -1;
    printf("%d\n", ret[n][f] = solve(n, f));
  }
  return 0;
}
