// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

#define I __int128

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

I c1, c2, e1, e2, P;

I exgcd(I a, I b, I &x, I &y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	LL d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

I inv(I a) {
	I A, B;
	exgcd(a, P, A, B);
	return (A % P + P) % P;
}

I power(I a, I b) {
    if (b < 0) return power(inv(a), -b);
	I ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % P;
		a = a * a % P;
		b >>= 1;
	}
	return ret;
}

int main() {
	int T; read(T);
	while (T--) {
		read(c1), read(c2), read(e1), read(e2); read(P);
		I A, B;
		I o = exgcd(e1, e2, A, B);
		I ans = power(c1, A) * power(c2, B) % P;
		printf("%lld\n", (LL)ans);
	}
    return 0;
}