#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <queue>
#include <map>

#define li long long
#define forn(i, n) for (int i = 0; i < (int) n; ++i)
#define all(a) a.begin(), a.end()

using namespace std;

inline void boost() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

li modexp(li x, li y, li N)
{
	if (y == 0) return 1;
	li z = modexp(x, y / 2, N);
	if (y % 2 == 0)
		return (z * z) % N;
	else
		return (((x * z) % N) * z) % N;
}
const li MOD = 1e9;
const li MOD2 = 1e9 + 13;

int main() {
	boost();
	int t;
	cin >> t;
	while (t--)
	{
		li n, k;
		cin >> k >> n;
		li F = modexp(k, n, MOD2);
		string ans = to_string(F);
		if (ans.length() >= 5)
			for (int i = ans.length() - 5; i < ans.length(); ++i)
				cout << ans[i];
		else
			cout << ans;
		cout << endl;


	}

}