#include <bits/stdc++.h>
using namespace std;
long long jie[100010], ni[100010];
int miu[100010];
long long power(long long x, int y) {
  if (y == 1)
    return x;
  else {
    long long tmp = power(x, y / 2);
    tmp = tmp * tmp % 1000000007;
    if (y % 2 == 1)
      return tmp * x % 1000000007;
    else
      return tmp;
  }
}
void initc() {
  int i;
  jie[0] = ni[0] = 1;
  for (i = 1; i < 100010; i++)
    jie[i] = jie[i - 1] * i % 1000000007, ni[i] = power(jie[i], 1000000007 - 2);
}
void initf() {
  int i, j, x;
  miu[1] = 1;
  long long y;
  for (i = 2; i < 100010; i++) {
    if (miu[i] != 0) continue;
    for (x = 1; x <= 100010 / i; x++)
      if ((miu[x] == 1 || miu[x] == -1) && (x % i != 0)) {
        miu[x * i] = 0 - miu[x];
        y = x * i;
        for (j = 1; j < 30; j++) {
          y = y * i;
          if (y > 100010) break;
          miu[y] = 2;
        }
      } else if (miu[x] == 2) {
        y = x;
        for (j = 1; j < 30; j++) {
          y *= i;
          if (y > 100010) break;
          miu[y] = 2;
        }
      }
  }
}
long long get(int x, int y) {
  long long ans = 1;
  if (x < y) return 0;
  ans = jie[x - 1] * ni[x - y] % 1000000007 * ni[y - 1] % 1000000007;
  return ans;
}
int main() {
  int q, x, y, i, j;
  initc();
  initf();
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &x, &y);
    long long ans = 0;
    for (i = 1; i * i <= x; i++)
      if (x % i == 0) {
        if (miu[i] == 1)
          ans = (ans + get(x / i, y)) % 1000000007;
        else if (miu[i] == -1)
          ans = (ans - get(x / i, y) + 1000000007) % 1000000007;
        if (i * i != x) {
          if (miu[x / i] == 1)
            ans = (ans + get(i, y)) % 1000000007;
          else if (miu[x / i] == -1)
            ans = (ans - get(i, y) + 1000000007) % 1000000007;
        }
      }
    printf("%d\n", ans);
  }
  return 0;
}
