#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  int f = 1;
  x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
const int N = 100000 + 5;
const int mo = 1000000007;
int T, n, k;
int vis[N];
long long fac[N], inv[N];
long long f[N];
vector<int> v[N];
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= x * (a / b);
}
void pre() {
  int K = 100000;
  long long y;
  fac[0] = 1;
  for (int i = 1; i <= K; i++) fac[i] = fac[i - 1] * i % mo;
  for (int i = 0; i <= K; i++) exgcd(fac[i], mo, inv[i], y);
  for (int i = 2; i <= K; i++) {
    for (int j = i; j <= K; j += i) {
      v[j].push_back(i);
    }
  }
}
long long C(int a, int b) {
  if (b > a) return 0;
  long long res = fac[a] * inv[b] % mo * inv[a - b] % mo;
  return res;
}
long long calc(int x) {
  if (vis[x] == T) return f[x];
  long long tmp = C(x - 1, k - 1);
  for (int i = 0; i < v[x].size(); i++) (tmp -= calc(x / v[x][i])) %= mo;
  f[x] = tmp;
  vis[x] = T;
  return f[x];
}
int main() {
  read(T);
  pre();
  memset(vis, 0, sizeof(vis));
  while (T) {
    read(n), read(k);
    printf("%lld\n", (calc(n) + mo) % mo);
    T--;
  }
  return 0;
}
