#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);
}

const double pi = acos(-1);
const long long INF = 1e17 + 13;
const li N = 1e5;

inline li mult(li a, li b) {
	return (a * b) % N;
}

inline li binpow(li k, li n) {
	li ans = 1;
	while (n > 0) {
		if (n % 2 == 1) {
			ans = mult(ans, k);
		}
		n /= 2;
		k = mult(k, k);
	}
	return ans;
}

int ans[220];
int main() {
	boost();

	int t;
	cin >> t;
	while (t--) {
		long long k, n;
		cin >> k >> n;

		li ans = binpow(k, n);
		if (ans != 0) {
			cout << binpow(k, n) % N;
		}
		else {
			for (int i = 0; i < 5; i++) {
				cout << 0;
			}
		}
		if (t != 0) {
			cout << endl;
		}
	}
}