/**
 *  winners never quit
**/

#include <bits/stdc++.h>
using namespace std;

const int N = 1e8;

long long mod = 1e9 + 7;

long long power(long long b, long long p){
  if (p==0)return 1LL % mod;
  if (p%2)return ((power(b, p-1)%mod) * (b%mod)) % mod;
  long long m = power(b, p/2);
  return ((m%mod)*(m%mod)) % mod;
}

vector <bool> mark(N+1, false);
vector <int> prime;

void sieve(){
  prime.push_back(2);
  for (long long i = 3;i <= N;i += 2){
    if (mark[i])continue;
    prime.push_back(i);
    for (long long j = i*i;j <= N;j += i+i){
      mark[j] = true;
    }
  }
}

vector <pair <long long, int> > pd;

void prime_div(long long n){
  for (int i = 0;i < prime.size();i++){
    long long temp = prime[i];
    if (temp*temp > n)break;
    if (n%temp==0){
      int cnt = 0;
      while (n%temp==0){
        n /= temp;
        cnt++;
      }
      pd.push_back({temp, cnt});
    }
  }
  if (n > 1)pd.push_back({n, 1});
}

vector <long long> all_div;

void find_all(){
  vector <long long> di;
  for (int i = 0;i < pd.size();i++){
    for (int j = 0;j < pd[i].second;j++){
      di.push_back(pd[i].first);
    }
  }
  int len = (1 << di.size());
  map <long long, int> mp;
  for (int i = 0;i < len;i++){
    long long cur = 1;
    for (int j = 0;j < di.size();j++){
      if (i & (1<<j))cur *= di[j];
    }
    if (!mp[cur])all_div.push_back(cur);
    mp[cur]++;
  }
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tc, ca = 0;
  sieve();
  cin >> tc;
  while (tc--){
    long long n, k;
    cin >> n >> k;
    prime_div(n);
    find_all();
    long long ans = 0;
    for (int i = 0;i < all_div.size();i++){
      ans = ((ans%mod) + power(all_div[i], k)) % mod;
    }
    cout << ans << '\n';
    pd.clear();
    all_div.clear();
  }
  return 0;
}