#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
long long add(long long a, long long b) {
  long long ans = a + b;
  ans += mod;
  return (ans % mod);
}
long long mul(long long a, long long b) {
  long long ans = a * b;
  ans += mod;
  return (ans % mod);
}
int mm[1000005][21];
vector<int> f;
int p[1000005][21];
int oe[1000005][2];
long long dp(int x, int y) {
  if (y == 1) {
    if (x == 1) return (0);
    return (1);
  }
  if (mm[x][y] != -1) return (mm[x][y]);
  long long ans = 0;
  for (auto v : f) {
    if (v > x) break;
    if (x % v) continue;
    ans = add(ans, dp(x / v, y - 1));
  }
  mm[x][y] = ans;
  return (ans);
}
int main() {
  int q;
  scanf("%d", &q);
  memset(mm, -1, sizeof(mm));
  memset(p, 0, sizeof(p));
  p[0][0] = 1;
  for (int i = 1; i < 1000005; i++) {
    for (int j = 0; j <= min(i, 20); j++) {
      p[i][j] = p[i - 1][j];
      if (j) {
        p[i][j] = add(p[i][j], p[i - 1][j - 1]);
      }
    }
  }
  memset(oe, 0, sizeof(oe));
  oe[0][0] = 1;
  for (int i = 1; i < 1000005; i++) {
    oe[i][0] = add(oe[i - 1][0], oe[i - 1][1]);
    oe[i][1] = add(oe[i - 1][0], oe[i - 1][1]);
  }
  while (q > 0) {
    q--;
    f.clear();
    int x, y;
    scanf("%d %d", &x, &y);
    if (x == 1) {
      printf("%d\n", oe[y][0]);
      continue;
    }
    for (int i = 2; i <= sqrt(x); i++) {
      if (x % i) continue;
      f.push_back(i);
      int j = x / i;
      if (j != i) f.push_back(j);
    }
    sort(f.begin(), f.end());
    int ans = 0;
    for (int i = 1; i <= min(y, 20); i++) {
      ans = add(ans, mul(mul(dp(x, i), p[y][i]), oe[y][0]));
    }
    printf("%d\n", ans);
  }
  return (0);
}
