It is holi festival, festival of colors. Devu is having fun playing holi and is throwing balloons with his girlfriend Glynis. Police saw this mischief and tried arresting his girlfriend, Devu being a mathematician asked police not to arrest his girlfriend and instead torture him with brain teaser. Devu was a young engineering fellow and he did not knew that policeman was equally good in mathematics, policeman gave Devu a problem which is as follows:

Let $f(n,k)=n^k$

Your aim is to answer $f(n_1,k_1)^{f(n_2,k_2)}\:\text{mod}\:n$

Can you help devu and his girlfriend rescue from modern police.

Input Format

You are given ${T}$ which is the number of queries to solve.

Each Query consist of 5 space separated integers $n_{1},k_{1},n_{2},k_{2},n$

Constraints

$1\leq T\leq10^4$       
$0\leq n_1,k_1,n_2,k_2\leq10^9$       
$1\leq n\leq10^7$

Note The output to ${{0}^{{0}$ should be ${1}$. 

Output Format

Output contains exactly ${T}$ lines. $i^{\cdot th}$ line containing the answer for the $i^{\cdot th}$ query.

Sample Input
1
2 1 2 2 15

Sample Output
1

Explanation

$f(2,1)=2$

$f(2,2)=4$

so answer is $16\:\text{mod}\:15=1$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


import os
import sys

def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


from math import log
from functools import lru_cache

@lru_cache(maxsize=None)
def factor(n):
	D = []
	m = 0
	while n & 1 == 0:
		m += 1
		n >>= 1
	if m > 0:
		D.append((2, m))
	d = 3
	while d * d <= n:
		m = 0
		while n % d == 0:
			m += 1
			n //= d
		if m > 0:
			D.append((d, m))
		d += 2
	if n > 1:
		D.append((n, 1))
	return D

def bezout(a, b):
	if b == 0:
		return (a, 1, 0)
	(g, u, v) = bezout(b, a % b)
	return (g, v, u - a // b * v)

def rev_chinois(a, p, b, q):
	(_, u, v) = bezout(p, q)
	return (b * u * p + a * v * q) % (p * q)

def main():
	T = int(input())
	for _ in range(T):
		(X, A, Y, B, M) = map(int, input().split())
		if B == 0:
			Y = B = 1
		if A == 0 or Y == 0:
			res = 1 % M
		else:
			DM = factor(M)
			(res, mod) = (0, 1)
			for (p, e) in DM:
				pe = p ** e
				x = 0
				if X % p == 0:
					if log(A) + B * log(Y) < log(e):
						x = pow(X, A * Y ** B, pe)
				else:
					phi = (p - 1) * pe // p
					x = pow(X, A * pow(Y, B, phi) % phi, pe)
				res = rev_chinois(res, mod, x, pe)
				mod *= pe
		print(res)
main()


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


import os
import sys

def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


import math
import os
import random
import re
import sys
lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


import math
import os
import random
import re
import sys

def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


import math
import os
import random
import re
import sys
prime = []
final_list = [0] + [0] + [1] * 3199
for i in range(2, 3201):
	if final_list[i] == 0:
		continue
	prime.append(i)
	for j in range(i * i, 3201, i):
		final_list[j] = 0

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def divisor(num):
	for p in prime:
		if p * p <= num and num % p == 0:
			while num % p == 0:
				num //= p
			yield p
	if num > 1:
		yield num
t = int(input().strip())
for t_itr in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	n1 = n1 % n
	if k1 == 0 or (n2 == 0 and k2 != 0):
		print(1 % n)
		continue
	elif n1 == 0:
		print(0)
		continue
	f1 = pow(n1, k1, n)
	gc = gcd(f1, n)
	n_new = n // gc
	totient = n_new
	for p in divisor(n_new):
		totient -= totient // p
	ans = pow(n2, k2, totient) - 1
	print(gc * (pow(f1, ans, n_new) * f1 // gc % n_new))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


import math
import os
import random
import re
import sys
lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


def EulerPhi(n):
	phi = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			phi -= phi // i
		while n % i == 0:
			n = n // i
		if i != 2:
			i += 2
		else:
			i += 1
	if n > 1:
		phi -= phi // n
	return phi

def solve(n1, k1, n2, k2, n):
	if k1 == 0 or (n2 == 0 and k2 != 0):
		return pow(n1, 0, n)
	if n2 == 1 or k2 == 0:
		return pow(n1, k1, n)
	if n1 == 0 or n1 % n == 0:
		return 0
	if k2 == 1:
		return pow(n1, k1 * n2, n)
	phi = EulerPhi(n)
	e = pow(n2, k2, phi) + phi
	return pow(pow(n1, k1, n), e, n)
t = int(input())
for _ in range(t):
	(n1, k1, n2, k2, n) = map(int, input().split())
	print(solve(n1, k1, n2, k2, n))


lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
	if mark[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		mark[j] = 1

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f
T = int(input())
for t in range(T):
	(n1, k1, n2, k2, n) = map(int, input().split())
	if n1 == 0:
		f1 = 1 if k1 == 0 else 0
	else:
		f1 = pow(n1, k1, n) or n
	if n2 == 0:
		f2 = 1 if k2 == 0 else 0
	else:
		phi = 1
		for (p, e) in factor(n).items():
			phi *= (p - 1) * p ** (e - 1)
		f2 = pow(n2, k2, phi) or phi
	print(pow(f1, f2, n))