#include <bits/stdc++.h>
using namespace std;
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
int color, vis[100009];
long long dp[100009];
long long F[100009], P[100009];
long long mod(long long x) {
  while (x < 0) x += 1000000007;
  return (x % 1000000007);
}
long long Fe(long long x, int y) {
  if (!y) return 1LL;
  long long h = Fe(x, y / 2);
  h = mod(h * h);
  if (y & 1) h = mod(h * x);
  return h;
}
long long C(int x, int y) {
  if (y > x) return 0;
  return mod(mod(F[x] * P[y]) * P[x - y]);
}
vector<int> dv[100009];
long long rec(int x, int y) {
  if (x <= y) return (x == y);
  long long& ret = dp[x];
  if (vis[x] == color) return ret;
  vis[x] = color;
  ret = C(x - 1, y - 1);
  for (typeof((dv[x]).begin()) it = (dv[x]).begin(); it != (dv[x]).end(); it++)
    ret = mod(ret - rec(x / (*it), y));
  return ret;
}
int main() {
  F[0] = P[0] = 1LL;
  for (int i = 2; i < 100009; i++)
    for (int j = i; j < 100009; j += i) dv[j].push_back(i);
  for (int i = 1; i < 100009; i++) {
    F[i] = mod(F[i - 1] * i);
    P[i] = Fe(F[i], 1000000007 - 2);
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int n, f;
    scanf("%d%d", &n, &f);
    color++;
    printf("%lld\n", rec(n, f));
  }
  return 0;
}
