#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 256;
const char nxtl = '\n';
const int mod = (int)1e9 + 7;
const double eps = (double)1e-9;
template <typename T>
inline bool updmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool updmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
int f[MAXN], inv[MAXN];
inline int binpow(int x, int y) {
  int res = 1;
  for (; y > 0; y >>= 1) {
    if (y & 1) res = (res * 1ll * x) % mod;
    x = (x * 1ll * x) % mod;
  }
  return res;
}
inline int cnk(int x, int y) {
  return (f[x] * 1ll * inv[y]) % mod * 1ll * inv[x - y] % mod;
}
inline void prec() {
  f[0] = 1;
  inv[0] = 1;
  for (int i = 1; i <= (int)1e5; ++i) {
    f[i] = f[i - 1] * 1ll * i % mod;
    inv[i] = binpow(f[i], mod - 2);
  }
}
map<pair<int, int>, int> dp;
int solve(int n, int k) {
  if (n < k) return 0;
  if (k == 1) return (n == 1);
  if (dp.count(make_pair(n, k))) return dp[make_pair(n, k)];
  int res = cnk(n - 1, k - 1);
  for (int i = 2; i * i <= n; ++i) {
    if (n % i > 0) continue;
    res -= solve(n / i, k);
    if (res < 0) res += mod;
    if (i * i != n) res -= solve(n / (n / i), k);
    if (res < 0) res += mod;
  }
  return dp[make_pair(n, k)] = res;
}
int main() {
  prec();
  int q;
  scanf("%d", &q);
  while (q-- > 0) {
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d\n", solve(n, k));
  }
  return 0;
}
