#include <bits/stdc++.h>
using namespace std;
long long int f[100001];
long long int invf[100001];
int count_factors[100001];
vector<int> factors[100001];
bool isprime[100001];
long long int power(long long int b, long long int e) {
  if (e == 0) {
    return 1;
  } else if (e == 1) {
    return b;
  } else {
    long long int p = power(b, e / 2);
    if (e % 2 == 0) {
      return (p * p) % 1000000007;
    } else {
      p = (p * p) % 1000000007;
      p = (p * b) % 1000000007;
      return p;
    }
  }
}
void init() {
  f[0] = 1LL;
  for (int i = 1; i <= 100000; i++) {
    f[i] = (i * f[i - 1]) % 1000000007;
  }
  invf[100000] = power(f[100000], 1000000007 - 2);
  for (int i = 99999; i >= 1; i--) {
    invf[i] = ((i + 1) * invf[i + 1]) % 1000000007;
  }
  invf[0] = 1LL;
}
void init1() {
  for (int i = 2; i <= 100000; i++) {
    isprime[i] = true;
  }
  for (int i = 2; i <= 100000; i++) {
    if (isprime[i]) {
      factors[i].push_back(i);
      for (int j = i + i; j <= 100000; j = j + i) {
        isprime[j] = false;
        factors[j].push_back(i);
      }
    }
  }
}
long long int nCr(long long int n, long long int r) {
  if (r > n) {
    return 0;
  } else {
    long long int temp = f[n];
    temp = (temp * invf[r]) % 1000000007;
    temp = (temp * invf[n - r]) % 1000000007;
    return temp;
  }
}
int main() {
  int q;
  scanf("%d", &q);
  init();
  init1();
  while (q--) {
    int n, f;
    scanf("%d%d", &n, &f);
    if (f == 1 && n != 1) {
      printf("0\n");
      continue;
    } else if (f == 1 && n == 1) {
      printf("1\n");
      continue;
    }
    long long int answer = 0;
    int size1 = factors[n].size();
    for (int i = 0; i < (1 << size1); i++) {
      int bitcount = 0;
      long long int temp1 = 1;
      for (int j = 0; j < size1; j++) {
        if (i & (1 << j)) {
          bitcount++;
          temp1 = temp1 * factors[n][j];
        }
      }
      if (bitcount % 2 == 1) {
        answer =
            ((answer - nCr(n / temp1 - 1, f - 1)) % 1000000007 + 1000000007) %
            1000000007;
      } else {
        answer = (answer + nCr(n / temp1 - 1, f - 1)) % 1000000007;
      }
    }
    printf("%lld\n", answer);
  }
  return 0;
}
