#include<bits/stdc++.h>
using namespace std;
long long p = 1000000007;
long long ans = 0;
void qpow(long long base,long long power){
  long long int result = 1;
		while (power > 0)
		{
			if (power & 1)
				result = result * base % p;
			base = base * base % p;     						
			power >>= 1;
		}
		ans += result % p;
		ans %= p;
}
void get_divisors(long long n, long long power) {
	for (long long i = 1;i <= n / i;i++) {
		if (n % i == 0) {
			qpow(i,power);
			if (n / i != i) 
      qpow(n/i,power);
		}
	}
}
int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	for (int i = 0;i < t;i++)
	{
		long long n, k;
    ans=0;
		cin >> n >> k;
		get_divisors(n, k);
		cout << ans << endl;
	}
	return 0;
}