C++ :

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
#define ll long long
#define ld long double
using namespace std;
ll c1, c2, e1, e2, n, x, y;
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll inv(ll a, ll b) {
    ll x, y;
    exgcd(a, b, x, y);
    return (x % b + b) % b;
}
ll ksc(ll x, ll y, ll mod) {
    ll t = x * y - (ll)((ld)x / mod * y + 0.5) * mod;
    return t < 0 ? t + mod : t;
}
ll ksm(ll x, ll y, ll mod) {
    ll s = 1;
    for (; y; y >>= 1, x = ksc(x, x, mod))
        if (y & 1)
            s = ksc(s, x, mod);
    return s;
}
void solve() {
    scanf("%lld%lld%lld%lld%lld", &c1, &c2, &e1, &e2, &n);
    exgcd(e1, e2, x, y);
    if (x < 0)
        c1 = ksm(inv(c1, n), -x, n);
    else
        c1 = ksm(c1, x, n);
    if (y < 0)
        c2 = ksm(inv(c2, n), -y, n);
    else
        c2 = ksm(c2, y, n);
    printf("%lld\n", ksc(c1, c2, n));
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
}