#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, mN = 1e5 + 100;
int add(int a, int b) {
  a += b;
  if (a < 0) a += mod;
  if (a >= mod) a -= mod;
  return a;
}
int mul(int a, int b) {
  long long ret = 1LL * a * b;
  if (ret >= mod) ret %= mod;
  return ret;
}
int pwm(int a, long long p) {
  int m = a, ret = 1;
  while (p) {
    if (p & 1) ret = mul(ret, m);
    m = mul(m, m);
    p >>= 1;
  }
  return ret;
}
int fact[mN];
int nCr(int n, int r) {
  if (r > n || r < 0) return 0;
  return mul(mul(fact[n], pwm(fact[n - r], mod - 2)), pwm(fact[r], mod - 2));
}
vector<int> primes;
int n, f;
void getprimes() {
  primes.clear();
  int tmp = n;
  for (int i = 2; i * i <= n; ++i) {
    if (tmp % i == 0) primes.push_back(i);
    while (tmp % i == 0) tmp /= i;
  }
  if (tmp > 1) primes.push_back(tmp);
}
int out = 0;
void solve(int idx, int v, int p) {
  if (idx == primes.size()) {
    if (p)
      out = add(out, -nCr(n / v - 1, f - 1));
    else
      out = add(out, nCr(n / v - 1, f - 1));
    return;
  }
  solve(idx + 1, v, p);
  solve(idx + 1, v * primes[idx], p ^ 1);
}
int main() {
  fact[0] = 1;
  for (int i = 1; i < mN; ++i) fact[i] = mul(fact[i - 1], i);
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    scanf("%d", &n), scanf("%d", &f);
    out = 0;
    getprimes();
    solve(0, 1, 0);
    printf("%d\n", out);
  }
}
