#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
template <class T>
T gcd(T x, T y) {
  while (T t = x % y) x = y, y = t;
  return y;
}
const double eps = 1e-9;
const double PI = acos(-1.);
const int INF = 1000000000;
const int MOD = 1000000007;
const double E = 2.7182818284590452353602874713527;
bool isdig(char x) { return x >= '0' && x <= '9'; }
bool isup(char x) { return x >= 'A' && x <= 'Z'; }
bool isdown(char x) { return x >= 'a' && x <= 'z'; }
bool islet(char x) { return isup(x) || isdown(x); }
int N, M;
vector<int> fac[100005];
vector<int> ffac[100005];
bool del[100005];
long long jc[100005];
void pre() {
  jc[0] = jc[1] = 1;
  for (int i = 2; i <= 100000; i++) {
    jc[i] = jc[i - 1] * i % MOD;
  }
  for (int i = 2; i <= 100000; i++) {
    if (ffac[i].size()) continue;
    for (int j = i; j <= 100000; j += i) {
      ffac[j].push_back(i);
    }
  }
  for (int i = 2; i <= 100000; i++) {
    if (del[i]) continue;
    if (i < 1000 && fac[i].size() == 0) {
      int d = i * i;
      for (int j = d; j <= 100000; j += d) del[j] = true;
    }
    for (int j = i; j <= 100000; j += i) {
      fac[j].push_back(i);
    }
  }
}
void get_data() { scanf("%d%d", &N, &M); }
long long fpow(long long x, int n) {
  long long r = 1;
  while (n) {
    if (n & 1) {
      r *= x;
      r %= MOD;
    }
    n >>= 1;
    x *= x;
    x %= MOD;
  }
  return r;
}
long long cal(int x, int y) {
  x--;
  y--;
  if (x < y) return 0;
  return jc[x] * fpow(jc[y], MOD - 2) % MOD * fpow(jc[x - y], MOD - 2) % MOD;
}
void run() {
  long long r = cal(N, M);
  for (int i = 0; i < fac[N].size(); i++) {
    if (ffac[fac[N][i]].size() & 1)
      r -= cal(N / fac[N][i], M);
    else
      r += cal(N / fac[N][i], M);
    r %= MOD;
    r += MOD;
    r %= MOD;
  }
  cout << r << endl;
}
int main() {
  pre();
  int t;
  t = 1;
  cin >> t;
  while (t--) {
    get_data();
    run();
  }
  return 0;
}
