#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
int fact[MAX_N], ive_fact[MAX_N];
std::vector<int> ver;
int pow(int a, int x) {
  int res = 1;
  while (x) {
    if (x & 1) res = 1ll * res * a % MOD;
    x >>= 1;
    a = 1ll * a * a % MOD;
  }
  return res;
}
int calc(int n, int k) {
  if (n < k) return 0;
  int res = fact[n];
  res = 1ll * res * ive_fact[k] % MOD;
  res = 1ll * res * ive_fact[n - k] % MOD;
  return res;
}
void Cnk_init() {
  fact[0] = 1;
  for (int i = 1; i < MAX_N; i++) fact[i] = 1ll * fact[i - 1] * i % MOD;
  for (int i = 0; i < MAX_N; i++) ive_fact[i] = pow(fact[i], MOD - 2);
}
void get_division(int n) {
  ver.clear();
  int final = sqrt((double)n + 0.5);
  for (int i = 2; i <= final; i++)
    if ((n % i) == 0) {
      ver.push_back(i);
      while ((n % i) == 0) n /= i;
    }
  if (n > 1) ver.push_back(n);
}
int main() {
  Cnk_init();
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    int n, f;
    scanf("%d%d", &n, &f);
    get_division(n);
    int ans = 0;
    for (int i = 0; i < (1 << ver.size()); i++) {
      int tmp = 1, sign = 1;
      for (int j = 0; j < ver.size(); j++)
        if (i & (1 << j)) {
          sign = -sign;
          tmp *= ver[j];
        }
      ans = (1ll + ans + MOD - 1 + sign * calc(n / tmp - 1, f - 1)) % MOD;
    }
    printf("%d\n", ans);
  }
}
