Little Panda has a thing for powers and modulus and he likes challenges. His friend Lucy, however, is impractical and challenges Panda to find both positive and negative powers of a number modulo a particular number. We all know that $A^{-1}\:{mod}\:X$ refers to the modular inverse of ${A}$ modulo ${X}$ (see Wikipedia).  

Since Lucy is impractical, she says that $A^{-n}\ \text{mod}\ X=(A^{-1}\ \text{mod}\ X)^n\ \text{mod}\ X$ for $n>0$.  

Now she wants Panda to compute $A^B\:{mod}\:X$.   

She also thinks that this problem can be very difficult if the constraints aren't given properly. Little Panda is very confused and leaves the problem to the worthy programmers of the world. Help him in finding the solution.

Input Format 

The first line contains ${T}$, the number of test cases. 

Then ${T}$ lines follow, each line containing ${A}$, ${B}$ and ${X}$.  

Output Format 

Output the value of $A^B\:{mod}\:X$.  

Constraints 

$1\leq T\leq1000$ 

$1\leq A\leq10^6$ 

$-10^6\leq B\leq10^6$ 

$1\leq X\leq10^6$ 

${A}$  and ${X}$ are coprime to each other (see Wikipedia)  

Sample Input  

3  
1 2 3  
3 4 2  
4 -1 5

Sample Output  

1  
1  
4  

Explanation 

Case 1: $1^2\ \text{mod}\ 3=1\ \text{mod}\ 3=1$ 

Case 2: $3^4\:\text{mod}\:2=81\:\text{mod}\:2=1$ 

Case 3: $4^{-1}\:\text{mod}\:5=4$

Difficulty: MEDIUM_HARD
Tags: Number theory

Starter code:

Solutions:
t = int(input())

def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m

def f(a, b, p):
	if b < 0:
		a = modinv(a, p)
		b = -b
	return pow(a, b, p)
for _ in range(t):
	(a, b, p) = map(int, input().split())
	print(f(a, b, p))


def ext_gcd(aneek, sayantan):
	ash = aneek // sayantan
	champa = aneek - sayantan * ash
	shreejit = [1, 0]
	while champa != 0:
		aneek = sayantan
		sayantan = champa
		shreejit.append(shreejit[0] - ash * shreejit[1])
		shreejit = shreejit[1:]
		ash = aneek // sayantan
		champa = aneek - sayantan * ash
	return shreejit[1]

def inv_mod(xavi, prime):
	barca = ext_gcd(xavi, prime)
	if barca < 0:
		barca += prime
	return barca
t = int(input())
for _ in range(t):
	l = list(map(int, input().strip().split()))
	a = l[0]
	b = l[1]
	p = l[2]
	if b < 0:
		c = inv_mod(a, p)
		b = abs(b)
		ans = pow(c, b, p)
	else:
		ans = pow(a, b, p)
	print(ans)


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
t = int(input())
for count in range(t):
	(a, b, x) = [t(s) for (t, s) in zip((int, int, int), input().split())]
	if b < 0:
		(a, b) = (modinv(a, x), -b)
	print(pow(a, b, x))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m
cases = int(input())
for i in range(cases):
	results = list(map(int, input().split()))
	A = results[0]
	B = results[1]
	X = results[2]
	if B >= 0:
		output = pow(A, B, X)
		print(int(output))
	else:
		first = modinv(A, X)
		output = pow(first, B * -1, X)
		print(int(output))


def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
for i in range(int(input())):
	l = [int(j) for j in input().split()]
	if l[1] >= 0:
		ans = pow(l[0], l[1], l[2])
	else:
		ans = pow(modinv(l[0], l[2]), -l[1], l[2])
	print(ans)


def mod_pow(base, exp, mod):
	res = 1
	base = base % mod
	while exp > 0:
		if exp % 2 == 1:
			res = res * base % mod
		exp = exp // 2
		base = base * base % mod
	return res

def mod_inv(a, mod):
	(t, nt) = (0, 1)
	(r, nr) = (mod, a)
	while nr > 0:
		q = r // nr
		(t, nt, r, nr) = (nt, t - q * nt, nr, r - q * nr)
	if t < 0:
		t += mod
	return t

def little_panda(b, e, m):
	if e < 0:
		e = -e
		b = mod_inv(b, m)
	return mod_pow(b, e, m)
t = int(input())
for i in range(t):
	(a, b, x) = map(int, input().strip().split())
	print(little_panda(a, b, x))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	else:
		return x % m

def mod_exp(a, b, q):
	p = a
	r = 1
	while b:
		if b & 1:
			r *= p
			r %= q
		p *= p
		p %= q
		b >>= 1
	return r
T = int(input())
for t in range(T):
	(A, B, X) = str(input()).split()
	(A, B, X) = (int(A), int(B), int(X))
	if B < 0:
		B = -B
		A = modinv(A, X)
	print(mod_exp(A, B, X))


def myf(a, b):
	x0 = 1
	y0 = 0
	x1 = 0
	y1 = 1
	x = 0
	y = 0
	while b != 0:
		v = a // b
		x = x0 - v * x1
		y = y0 - v * y1
		x0 = x1
		y0 = y1
		x1 = x
		y1 = y
		r = a % b
		a = b
		b = r
	return y0

def modinverse(a, b):
	return myf(a, b)

def mypower(a, b, x):
	if a == 1:
		return 1
	if b == 1:
		return a
	b1 = b // 2
	b2 = b % 2
	a1 = a * a % x
	a2 = 1
	if b2 == 1:
		a2 = a
	res = a2 * mypower(a1, b1, x) % x
	return res
t = int(input())
for t1 in range(t):
	(a, b, x) = [int(i) for i in input().strip().split()]
	a %= x
	res = 0
	if b >= 0:
		res = a
	else:
		res = modinverse(x, a)
		res = (res + x) % x
		b = -b
	if b > 100:
		res = mypower(res, b, x)
	else:
		res = res ** b % x
	print(res)


import sys

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def mod_inv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, X) = list(map(int, sys.stdin.readline().split()))
	if B < 0:
		A = mod_inv(A, X)
	print(pow(A, abs(B), X))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
T = int(input())
for _ in range(T):
	(a, b, x) = map(int, input().split())
	if b >= 0:
		print(pow(a, b, x))
	else:
		invA = modinv(a, x)
		print(pow(invA % x, abs(b), x))


def extended_euclid(a, b):
	if b == 0:
		return (a, 1, 0)
	(d, x, y) = extended_euclid(b, a % b)
	return (d, y, x - a // b * y)
for t in range(int(input())):
	(a, b, x) = [int(i) for i in input().split()]
	if b >= 0:
		print(pow(a, b, x))
	else:
		(gcd, inv_a, inv_x) = extended_euclid(a, x)
		print(pow(inv_a, -b, x))


def gcde(a, b):
	(r, u, v, r2, u2, v2) = (a, 1, 0, b, 0, 1)
	while r2 > 0:
		q = r // r2
		(r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)
	return (r, u, v)

def invMod(a, m):
	(r, u, v) = gcde(a, m)
	if r != 1:
		return None
	return u
T = int(input())
for _ in range(T):
	(A, B, X) = (int(_) for _ in input().split())
	if B < 0:
		A = invMod(A, X)
		B = -B
	print(pow(A, B, X))


def myf(a, b):
	x0 = 1
	y0 = 0
	x1 = 0
	y1 = 1
	x = 0
	y = 0
	while b != 0:
		v = a // b
		x = x0 - v * x1
		y = y0 - v * y1
		x0 = x1
		y0 = y1
		x1 = x
		y1 = y
		r = a % b
		a = b
		b = r
	return y0
t = int(input())
for t1 in range(t):
	(a, b, x) = [int(i) for i in input().strip().split()]
	a %= x
	res = 0
	if b >= 0:
		res = a
	else:
		res = myf(x, a)
		res = (res + x) % x
		b = -b
	print(pow(res, b, x))


def egcd(a, b):
	(x, y, u, v) = (0, 1, 1, 0)
	while a != 0:
		(q, r) = (b // a, b % a)
		(m, n) = (x - u * q, y - v * q)
		(b, a, x, y, u, v) = (a, r, u, v, m, n)
	gcd = b
	return (gcd, x, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m
T = int(input())
for i in range(T):
	(a, b, x) = [int(num) for num in input().split()]
	if b < 0:
		a = modinv(a, x)
	print(pow(a, abs(b), x))


import sys

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def mod_inv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, X) = list(map(int, sys.stdin.readline().split()))
	if B < 0:
		A = mod_inv(A, X)
	print(pow(A, abs(B), X))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	if b < 0:
		b = -b
		a = modinv(a, x)
	print(pow(a, b, x))


import sys

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def mod_inv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, X) = list(map(int, sys.stdin.readline().split()))
	if B < 0:
		A = mod_inv(A, X)
	print(pow(A, abs(B), X))


import sys

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def mod_inv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, X) = list(map(int, sys.stdin.readline().split()))
	if B < 0:
		A = mod_inv(A, X)
	print(pow(A, abs(B), X))


import sys

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def mod_inv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B, X) = list(map(int, sys.stdin.readline().split()))
	if B < 0:
		A = mod_inv(A, X)
	print(pow(A, abs(B), X))


def inverse(a, n):
	t = 0
	newt = 1
	r = n
	newr = a
	while newr != 0:
		quotient = r // newr
		(t, newt) = (newt, t - quotient * newt)
		(r, newr) = (newr, r - quotient * newr)
	if r > 1:
		return 'a is not invertible'
	if t < 0:
		t = t + n
	return t

def panda(a, b, x):
	if b > -1:
		print(pow(a, b, x))
	else:
		print(pow(inverse(a, x), abs(b), x))

def main():
	for i in range(int(input())):
		(a, b, x) = input().split()
		(a, b, x) = (int(a), int(b), int(x))
		panda(a, b, x)
main()


t = int(input())

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m
for _ in range(t):
	A = [int(x) for x in input().split()]
	r = pow(A[0], abs(A[1]), A[2])
	if A[1] >= 0:
		print(r)
	else:
		print(modinv(r, A[2]))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m

def main():
	t = int(input())
	for _ in range(t):
		(a, b, x) = list(map(int, input().split()))
		if b < 0:
			inverse = modinv(a, x)
			print(pow(inverse, -b, x))
		else:
			print(pow(a, b, x))
main()


def bezout(m, n):
	if n == 0:
		return (1, 0)
	tmp = bezout(n, m % n)
	return (tmp[1], tmp[0] - tmp[1] * (m // n))

def inv(m, n):
	return bezout(m, n)[0] % n

def modpow(m, n, x):
	if n < 0:
		return modpow(inv(m, x), -n, x)
	if n == 0:
		return 1
	if n == 1:
		return m % x
	p = modpow(m, n // 2, x)
	if n % 2:
		return p * p * m % x
	return p * p % x
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	print(modpow(a, b, x))


from math import floor

def extended_ucleadian_inverse(number, mod):
	r_0 = mod
	r_1 = number
	q_0 = 0
	q_1 = 1
	while 1:
		r = r_1
		quo = floor(r_0 / r_1)
		r_1 = r_0 % r_1
		r_0 = r
		if r_1 == 0:
			break
		q = q_1
		q_1 = (q_0 - q_1 * quo) % mod
		q_0 = q
	return q_1

def get_neg_mod(a, b, x):
	a = a % x
	if a == 0:
		return 1
	a_i = extended_ucleadian_inverse(a, x)
	return get_mod(a_i, -1 * b, x)

def modulo_break(a, power, x, i, res, b_bin):
	if power == 1:
		res[i] = a % x
		return res[i]
	res[i] = modulo_break(a, int(power / 2), x, i + 1, res, b_bin) % x
	res[i] = res[i] * res[i] % x
	return res[i]

def get_mod(a, b, x):
	if b >= 0:
		b_bin = bin(b)
		power = 2 ** (len(b_bin) - 3)
		res = [0] * len(b_bin)
		modulo_break(a, power, x, 2, res, b_bin)
		answer = 1
		for i in range(2, len(b_bin)):
			if b_bin[i] == '1':
				answer = answer * res[i] % x
	else:
		answer = get_neg_mod(a, b, x)
	return answer

def main():
	t = int(input())
	while t:
		abx = input().split()
		a = int(abx[0])
		b = int(abx[1])
		x = int(abx[2])
		answer = get_mod(a, b, x)
		print(answer)
		t -= 1
main()


def phi(n):
	res = n
	i = 2
	while i ** 2 <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			res -= res // i
		i += 1
	if n > 1:
		res -= res // n
	return res
for t in range(int(input())):
	(a, b, x) = list(map(int, input().split()))
	if x < 2:
		print(0)
		continue
	if b < 0:
		a = pow(a, phi(x) - 1, x)
		b *= -1
	print(pow(a, b, x))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(g, y, x) = egcd(b % a, a)
	return (g, x - b // a * y, y)

def modinv(a, m):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	return x % m
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	print(pow(a, b, x) if b >= 0 else pow(modinv(a, x), -b, x))


def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
for _ in range(int(input())):
	(a, b, x) = [int(ns) for ns in str(input()).split()]
	if x == 1:
		print(0)
		continue
	if b < 0:
		a = modinv(a, x)
		b = -b
	a = a % x
	S = 500
	if b > S:
		ans = a ** S % x
		ans = ans ** (b // S)
		ans = ans % x
		b = b % S
	else:
		ans = 1
	ans = ans * (a ** b % x)
	print(ans % x)


def euclid(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = euclid(b % a, a)
		return (g, x - b // a * y, y)
for i in range(int(input())):
	lst = input().split(' ')
	if int(lst[1]) > 0:
		power = pow(int(lst[0]), int(lst[1]), int(lst[2]))
		print(power)
	elif int(lst[1]) == 0:
		power = 1
		print(power)
	else:
		init = pow(int(lst[0]), -1 * int(lst[1]), int(lst[2]))
		n = euclid(init, int(lst[2]))
		power = n[1] % int(lst[2])
		print(power)


def inverse(y, z):
	(c, d, e, f) = (1, 0, 0, 1)
	while z > 0:
		(y, z, c, d, e, f) = (z, y % z, e, f, c - e * (y // z), d - f * (y // z))
	return int(c)
t = int(input().strip())
for j in range(t):
	(a, b, x) = [int(i) for i in input().strip().split(' ')]
	if b == 0:
		print(1)
		continue
	if b < 0:
		a = inverse(a, x)
		b = int(0 - b)
	print(int(pow(a % x, b, x)))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('eep')
	else:
		return x % m
for _ in range(int(input())):
	(a, b, x) = list(map(int, input().split()))
	if b >= 0:
		print(pow(a, b, x))
	else:
		print(pow(modinv(a, x), -b, x))


def egcd(a, b, mod):
	if b == 0:
		return (1, 0)
	tmp = egcd(b, a % b, mod)
	return (tmp[1], (mod + tmp[0] - a // b * tmp[1]) % mod)
t = int(input())
for _ in range(t):
	(a, b, x) = map(int, input().split())
	if b >= 0:
		print(pow(a, b, x))
	else:
		a_inv = egcd(a, x, x)[0]
		print(pow(a_inv, -b, x))


MAXN = 10 ** 6 + 1
isPrime = [True] * MAXN
primes = []
for i in range(2, MAXN):
	if not isPrime[i]:
		continue
	for j in range(i + i, MAXN, i):
		isPrime[j] = False
	primes.append(i)

def modpow(a, b, m):
	acc = 1
	curpow = a
	while b > 0:
		if b & 1:
			acc = acc * curpow % m
		curpow = curpow ** 2 % m
		b >>= 1
	return acc

def totient(m):
	acc = m
	for p in primes:
		if p > m:
			break
		if m % p == 0:
			acc = acc * (p - 1) // p
	return acc

def invmod(a, m):
	return modpow(a, totient(m) - 1, m)
for _ in range(int(input())):
	(A, B, X) = map(int, input().strip().split())
	if B < 0:
		inv = invmod(A, X)
		print(modpow(inv, abs(B), X))
	else:
		print(modpow(A, B, X))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def compute_inverse(a, m):
	(_, x, _) = egcd(a, m)
	return x % m
cache = {}

def exponentiate(a, b, x):
	if (a, b, x) in cache:
		return cache[a, b, x]
	elif b == 0:
		return 1
	elif b == 1:
		return a % x
	elif b % 2 == 0:
		retval = exponentiate(a, b // 2, x) ** 2 % x
	else:
		retval = a * exponentiate(a, b // 2, x) ** 2 % x
	return retval
for _ in range(int(input())):
	(a, b, x) = [int(i) for i in input().split()]
	if b == 0:
		print(1)
	elif b < 0:
		print(exponentiate(compute_inverse(a, x), -b, x))
	else:
		print(exponentiate(a, b, x))


import sys

def xgcd(b, n):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)
t = int(input())
for _ in range(t):
	(a, b, x) = [int(x) for x in input().split()]
	if b < 0:
		(_, a, _) = xgcd(a, x)
		b = -b
	print(pow(a, b, x))


import sys

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def solve(a, b, m):
	if b >= 0:
		return pow(a, b, m)
	ai = modinv(a, m)
	print('a=%d m=%d ai=%d' % (a, m, ai), file=sys.stderr)
	return pow(ai, -b, m)
t = int(input())
for _ in range(t):
	(a, b, m) = map(int, input().split())
	print(solve(a % m, b, m))


T = int(input())
for t in range(T):
	splited = input().split(' ')
	A = int(splited[0])
	B = int(splited[1])
	X = int(splited[2])
	if B >= 0:
		print(pow(A, B, X))
	else:
		t = 0
		r = X
		newt = 1
		newr = A
		while newr != 0:
			q = int(r / newr)
			(t, newt) = (newt, t - q * newt)
			(r, newr) = (newr, r - q * newr)
		if r > 1:
			print('not invertible')
		if t < 0:
			t = t + X
		print(pow(t, -B, X))


def gcd_ext(a, b):
	s = 0
	t = 1
	while b:
		(q, r) = divmod(a, b)
		(s, t) = (t, s - q * t)
		(a, b) = (b, r)
	return s

def main():
	for i in range(int(input())):
		(a, b, m) = map(int, input().split())
		if b < 0:
			a = gcd_ext(m, a)
			b = -b
		print(pow(a, b, m))
main()


def mod_pow(a, n, m):
	a0 = a % m
	n0 = n
	res = 1
	while n0 > 0:
		if n0 & 1:
			res = res * a0 % m
		a0 = a0 * a0 % m
		n0 >>= 1
	return res

def extended_euclid(a, m):
	if m == 0:
		return (a, 1, 0)
	(d_, s_, t_) = extended_euclid(m, a % m)
	(d, s, t) = (d_, t_, s_ - a // m * t_)
	return (d, s, t)

def little_panda_power(a, b, x):
	if b < 0:
		b0 = -b
		a0 = extended_euclid(a, x)[1]
	else:
		b0 = b
		a0 = a
	return mod_pow(a0, b0, x)

def do_it():
	Ts = input()
	T = int(Ts)
	for i in range(T):
		abxs = input().split(' ')
		a = int(abxs[0])
		b = int(abxs[1])
		x = int(abxs[2])
		print(little_panda_power(a, b, x))
do_it()


def euclide(a, b):
	if a < 0:
		r = euclide(-a, b)
		return (r[0], -r[1], r[2])
	if b < 0:
		r = euclide(a, -b)
		return (r[0], r[1], -r[2])
	if b == 0:
		return (a, 1, 0)
	r = euclide(b, a % b)
	return (r[0], r[2], r[1] - a // b * r[2])
for _ in range(int(input())):
	(A, B, X) = map(int, input().split())
	if B < 0:
		A = euclide(A, X)[1]
		B = -B
	print(pow(A, B, X))


def prime_decompose(n):
	if n < 1:
		raise ValueError('input number is less than 1')
	res = dict()
	while n % 2 is 0:
		try:
			res[2] += 1
		except KeyError:
			res[2] = 1
		n //= 2
	divisor = 3
	while divisor <= n:
		while n % divisor is 0:
			try:
				res[divisor] += 1
			except KeyError:
				res[divisor] = 1
			n //= divisor
		divisor += 2
	return res

def f(n):
	p = prime_decompose(n)
	for i in p:
		n //= i
		n *= i - 1
	return n
for _ in range(int(input())):
	(a, b, x) = [int(i) for i in input().split()]
	if 0 <= b:
		print(pow(a, b, x))
	else:
		print(pow(a, -b * (f(x) - 1), x))


import sys

def gcd(a, b):
	if a > b:
		(m, x, y) = gcd(b, a)
		return (m, y, x)
	if a == 0:
		return (b, 0, 1)
	else:
		(x, y, z) = gcd(b % a, a)
		return (x, z - int(b / a) * y, y)

def mult_mod_inverse(a, m):
	(x, y, z) = gcd(a, m)
	if x == 1:
		return y
	else:
		raise Exception('no inverse')

def powmod(a, x, m):
	if x == 0:
		return 1
	else:
		return a ** (x % 2) * powmod(a * a % m, int(x / 2), m) % m
t = int(sys.stdin.readline())
for i in range(t):
	(a, b, x) = map(int, sys.stdin.readline().split())
	if b >= 0:
		print(powmod(a, b, x))
	else:
		print(powmod(mult_mod_inverse(a, x), -b, x))


def gcdex(a, p):
	n = p
	b = a
	(x0, x1) = (1, 0)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
	return x0 % p
T = int(input())
for i in range(T):
	(a, b, x) = (int(j) for j in input().split())
	if b < 0:
		a = gcdex(a, x)
		b = -b
	print(pow(a, b, x))


def main():
	t = int(input())
	for _ in range(t):
		(a, b, x) = map(int, input().split())
		if b == 0:
			print(1)
		elif b > 0:
			print(exponentiate(a, b, x))
		else:
			v = modularInverse(a, x) % x
			print(exponentiate(v, -b, x))

def modularInverse(a, m):
	m0 = m
	(x0, x1) = (0, 1)
	if m == 1:
		return 0
	while a > 1:
		q = int(a / m)
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += m0
	return x1

def exponentiate(a, n, m):
	while n % 2 == 0:
		a = a * a % m
		n = n / 2
	x = a % m
	n = int(n / 2)
	while n > 0:
		a = a * a % m
		if n % 2 == 1:
			x = x * a % m
		n = int(n / 2)
	x = x % m
	return x
main()


def power(a, b, x):
	res = 1
	mod = x
	while b:
		if b & 1:
			res = res * a % mod
		b = b >> 1
		a = a * a % mod
	return res

def gcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(g, x1, y1) = gcd(b % a, a)
	x = y1 - int(b / a) * x1
	y = x1
	return (g, x, y)
for test in range(int(input())):
	(a, b, x) = [int(x) for x in input().split()]
	if b >= 0:
		print(power(a, b, x))
	else:
		(g, x1, y1) = gcd(a, x)
		print(power(x1 % x, -b, x))


def modInverse(a, m):
	(x, y, g) = gcdExtended(a, m, 0, 0)
	res = -1
	if g != 1:
		print('Number Are Not Co Prime')
	else:
		res = (x % m + m) % m
	return res

def gcdExtended(a, b, x, y):
	if a == 0:
		return (0, 1, b)
	(x1, y1, gcd) = gcdExtended(b % a, a, x, y)
	x = y1 - int(b / a) * x1
	y = x1
	return (x, y, gcd)

def calModPow(a, b, m):
	a %= m
	result = 1
	while b > 0:
		if b & 1:
			result = result * a % m
		a = a * a % m
		b >>= 1
	return result
t = int(input().strip())
while t > 0:
	t -= 1
	(a, b, m) = [int(x) for x in input().strip().split(' ')]
	if b == -1:
		modInv = modInverse(a, m)
		print(modInv)
	elif b < -1:
		modInv = modInverse(a, m)
		b = b * -1
		print(calModPow(modInv, b, m))
	else:
		print(calModPow(a, b, m))


def inverse_mod(a, b):
	s = 0
	old_s = 1
	t = 1
	old_t = 0
	r = b
	old_r = a
	while r != 0:
		quotient = old_r // r
		(old_r, r) = (r, old_r - quotient * r)
		(old_s, s) = (s, old_s - quotient * s)
		(old_t, t) = (t, old_t - quotient * t)
	return old_s

def mod_pow(a, b, c):
	if b < 0:
		b = -b
		a = inverse_mod(a, c)
	return pow(a, b, c)
for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	print(mod_pow(a, b, c))


import math

def extEuclideanAlg(a, b):
	if b == 0:
		return (1, 0, a)
	else:
		(x, y, gcd) = extEuclideanAlg(b, a % b)
		return (y, x - y * (a // b), gcd)

def modInvEuclid(a, m):
	(x, y, gcd) = extEuclideanAlg(a, m)
	if gcd == 1:
		return x % m
	else:
		return None

def toPowerN(a, n, mod):
	if n == 0:
		return 1
	a = a % mod
	aPower2Powerk = {0: 1, 1: a}
	maxK = math.floor(math.log2(n)) + 1
	cur = a
	for k in range(1, maxK):
		cur = cur * cur % mod
		aPower2Powerk[2 ** k] = cur

	def internalToPowerN(a, n, mod, aPower2Powerk):
		if n == 0:
			return 1
		log2N = math.log2(n)
		if int(log2N in aPower2Powerk):
			return aPower2Powerk[n]
		log2N = math.floor(math.log2(n))
		baseN = 2 ** log2N
		return aPower2Powerk[baseN] * internalToPowerN(a, n - baseN, mod, aPower2Powerk) % mod
	return internalToPowerN(a, n, mod, aPower2Powerk)
t = int(input())
for i in range(t):
	(a, b, x) = map(int, input().split())
	if b >= 0:
		print(toPowerN(a, b, x))
	else:
		aI = modInvEuclid(a, x)
		print(toPowerN(aI, -b, x))


def egcd(a0, a1):
	(x0, x1, y0, y1, b, n) = (1, 0, 0, 1, a0, a1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def modinv(n, p):
	return egcd(n, p)[1] % p
T = int(input().strip())
for _ in range(T):
	(A, B, X) = list(map(int, input().strip().split()))
	if B >= 0:
		print(pow(A, B, X))
	else:
		print(pow(modinv(A, X), -B, X))


def modinv(a, x):
	(t, nt, r, nr) = [0, 1, x, a % x]
	while nr:
		q = r // nr
		(t, nt) = (nt, t - q * nt)
		(r, nr) = (nr, r - q * nr)
	if r > 1:
		return 0
	return t % x
T = int(input())
for _ in range(T):
	(A, B, X) = input().split()
	(A, B, X) = [int(A), int(B), int(X)]
	if X == 1:
		print(0)
	else:
		if B < 0:
			A = modinv(A, X)
		print(pow(A, abs(B), X))


def factor(n):
	factors = dict()
	d = 2
	while d * d <= n:
		while n % d == 0:
			factors[d] = factors.get(d, 0) + 1
			n //= d
		d += 1
	if n > 1:
		factors[n] = factors.get(n, 0) + 1
	return factors

def phi(n):
	factors = factor(n)
	ans = 1
	for (p, d) in factors.items():
		ans *= p ** d - p ** (d - 1)
	return ans
T = int(input())
for t in range(T):
	(A, B, X) = [int(x) for x in input().split()]
	print(pow(A, B % phi(X), X))


def gcd(a, b):
	oldr = a
	olds = 1
	oldt = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = oldr // r
		(r, oldr) = (oldr - q * r, r)
		(s, olds) = (olds - q * s, s)
		(t, oldt) = (oldt - q * t, t)
	return (oldr, olds, oldt)

def computePower(A, B, X):
	if B < 0:
		(g, s, t) = gcd(A, X)
		assert g == 1
		A = s
		if A < 0:
			A += X
		B = -B
	exp = 1
	power = A
	prod = 1
	while exp <= B:
		if B & exp:
			prod = prod * power % X
		exp *= 2
		power = power ** 2 % X
	return prod
line = input()
ctests = int(line)
for itest in range(ctests):
	line = input()
	tokens = line.split()
	A = int(tokens[0])
	B = int(tokens[1])
	X = int(tokens[2])
	print(computePower(A, B, X))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def mod_inv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m
T = int(input())
a = []
for _ in range(T):
	(A, B, X) = list(map(int, input().split()))
	if B < 0:
		A = mod_inv(A, X)
	a.append(pow(A, abs(B), X))
for i in range(len(a)):
	print(a[i])


def egcd(a, b):
	assert min(a, b) >= 0
	assert max(a, b) >= 1
	(x, sx, y, sy) = (a, 1, b, 0)
	while y > 0:
		r = x % y
		sr = sx - sy * ((x - r) // y)
		(x, sx, y, sy) = (y, sy, r, sr)
	assert y == 0
	tb = x - sx * a
	assert tb % b == 0
	return (x, sx, tb // b)

def modulo(a, n):
	assert n >= 1
	a %= n
	return a if a >= 0 else a + n

def inverse(a, n):
	(g, s, t) = egcd(a, n)
	if g == 1:
		return modulo(s, n)
	else:
		raise ValueError('no inverse exists')
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	if b < 0:
		(a, b) = (inverse(a, x), -b)
	print(pow(a, b, x))


def fast_expo(a, e, x):
	if e == 0:
		return 1
	if e % 2 == 0:
		return fast_expo(a, e // 2, x) ** 2 % x
	if e % 2 == 1:
		return a * fast_expo(a, e // 2, x) ** 2 % x

def xpgcd(a, b):
	(prev_u, u) = (1, 0)
	(prev_v, v) = (0, 1)
	while b != 0:
		q = a // b
		r = a % b
		(prev_u, u) = (u, prev_u - q * u)
		(prev_v, v) = (v, prev_v - q * v)
		(a, b) = (b, r)
	return (prev_u, prev_v)
T = int(input())
for i in range(T):
	(A, B, X) = [int(i) for i in str.split(input())]
	if B < 0:
		A = xpgcd(A, X)[0]
		B = -B
	if A == 0:
		print(0)
	else:
		res = fast_expo(A, B, X)
		print(res)


def mod_inv(x, y):
	(a1, r1) = (1, x % y)
	(a2, r2) = (0, y)
	while r2 != 1:
		q = r1 // r2
		(a1, a2) = (a2, a1 - q * a2)
		(r1, r2) = (r2, r1 - q * r2)
	return a2 % y
res = []
for _ in range(int(input())):
	(a, b, m) = map(int, input().split())
	if b >= 0:
		res.append(pow(a, b, m))
	else:
		res.append(pow(mod_inv(a, m), -b, m))
print(*res, sep='\n')


def minv(a, b):
	(prevx, x) = (1, 0)
	(prevy, y) = (0, 1)
	while b:
		q = a // b % X
		(x, prevx) = ((prevx - q * x) % X, x)
		(y, prevy) = ((prevy - q * y) % X, y)
		(a, b) = (b, a % b)
	return int(prevy)
T = int(input())
for t in range(T):
	(A, B, X) = [int(i) for i in input().split()]
	if B < 0:
		(A, B) = (minv(X, A), -B)
	x = 1
	v = A % X
	if B == 0:
		print(1)
	else:
		s = bin(B)[2:][::-1]
		n = len(s)
		if int(s[0]):
			x = v
		for i in range(1, n):
			v = v ** 2 % X
			if int(s[i]):
				x = x * v % X
		print(x)


def mpow(a, k, x):
	if k == 0:
		return 1
	p = mpow(a, k >> 1, x)
	p = p * p % x
	return [p, p * a % x][k & 1]

def mrev(a, x):
	(xa, xx) = (1, 0)
	while x:
		q = a // x
		r = a % x
		xr = xa - q * xx
		xa = xx
		xx = xr
		a = x
		x = r
	return xa
t = int(input())
for i in range(t):
	(a, b, x) = list(map(int, input().split()))
	if b >= 0:
		print(mpow(a, b, x))
	else:
		print(mpow(mrev(a, x), -b, x))


def f(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = f(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = f(a, m)
	return x % m

def solution(A, B, X):
	if B < 0:
		return pow(modinv(A, X), -B, X)
	else:
		return pow(A, B, X)

def main():
	T = int(input().strip())
	for i in range(T):
		(A, B, X) = input().strip().split()
		(A, B, X) = (int(A), int(B), int(X))
		print(solution(A, B, X))
main()


import sys
import math
arr2 = list(map(lambda x: x.strip(), sys.stdin.readlines()))

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
arr2.pop(0)
for line in arr2:
	arr = line.split()
	arr = [int(x) for x in arr]
	a = arr[0]
	b = arr[1]
	c = arr[2]
	if b < 0:
		b = b * -1
		a = modinv(a, c)
	if b == 0:
		print('1')
	elif b == 1:
		print(a)
	else:
		l = math.log(b, 2)
		l = math.floor(l)
		l2 = l
		s = ''
		while b > 0:
			if pow(2, l) <= b:
				s = s + '1'
				b = b - pow(2, l)
			else:
				s = s + '0'
			l = l - 1
		s = s + '0' * (l + 1)
		l = l2
		squares = []
		for i in range(l + 1):
			if i == 0:
				squares.append(a % c)
			else:
				squares.append(pow(squares[i - 1], 2) % c)
		squares.reverse()
		res = 1
		for i in range(l + 1):
			if s[i] == '1':
				res = res * squares[i] % c
		print(res)


def egcd(a, b):
	if a == 0:
		return (0, 1)
	if a > b:
		return egcd(b, a)
	else:
		(x, y) = egcd(b % a, a)
		return (y - b // a * x, x)
for _ in range(int(input())):
	(a, b, x) = [int(x) for x in input().split()]
	try:
		print(pow(a, b, x))
	except:
		print(pow(egcd(a, x)[a > x], -b, x))


def modular_inverse(a, b):
	if b > a:
		(a, b) = (b, a)
	s = []
	while b != 0:
		s.append((a, a // b))
		(a, b) = (b, a % b)
	final = a
	if final != 1:
		print('Not coprime.. Factor of {}'.format(final))
	(p, q) = s.pop()
	x0 = 1
	a0 = p
	x1 = -q + 1
	a1 = a
	while s:
		(p, q) = s.pop()
		factor = x1
		a1 = a0
		x1 = x0 - factor * q
		a0 = p
		x0 = factor
	return x1 % a0

def mult(x, y, m):
	return x * y % m

def test_modular_inverse():
	for prime in [7, 11, 13, 17, 53]:
		for i in range(1, prime):
			x = modular_inverse(prime, i)
			assert mult(x, i, prime) == 1
	print('Tested modular_inverse')

def efficient_pow(a, b, n):
	if b == 1:
		return a
	x = efficient_pow(a, b // 2, n)
	x = mult(x, x, n)
	if not b % 2:
		return x
	else:
		return mult(x, a, n)

def general_pow(a, b, n):
	if b == 0:
		return 1 % n
	if b < 0:
		a = modular_inverse(a, n)
		b *= -1
	return efficient_pow(a, b, n)
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	print(general_pow(a % n, b, n))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m
for i in range(int(input())):
	(a, b, x) = map(int, input().split())
	if b < 0:
		print(pow(modinv(a, x), -b, x))
	else:
		print(pow(a, b, x))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def power(a, b, x):
	if b < 0:
		return power(modinv(a, x), -b, x)
	result = 1
	carry = a
	while b > 0:
		if b & 1:
			result = result * carry % x
		carry = carry * carry % x
		b = b // 2
	return result
T = int(input())
for _ in range(T):
	(A, B, X) = map(int, input().split())
	print(power(A, B, X))


def pwr(b, p, m):
	b %= m
	if p == 0:
		return 1
	if p == 1:
		return b
	return pwr(b * b, p // 2, m) * pwr(b, p % 2, m) % m

def phi(n):
	res = n
	for i in range(2, n):
		if i * i > n:
			break
		if n % i == 0:
			res //= i
			res *= i - 1
			while n % i == 0:
				n //= i
	if n > 1:
		res *= n - 1
	return res
for _ in range(int(input())):
	(b, p, m) = map(int, input().split())
	if p >= 0:
		print(pwr(b, p, m))
	else:
		print(pwr(pwr(b, phi(m) - 1, m), -p, m))


def rv(a, b):
	if b == 0:
		d = a
		x = 1
		y = 0
	else:
		(d, x, y) = rv(b, a % b)
		(x, y) = (y, x - a // b * y)
	return (d, x, y)
t = int(input())
for i in range(t):
	(a, b, m) = map(int, input().split())
	d = 1
	if b > 0:
		s = bin(b)[2:]
		for j in s:
			if j == '1':
				d = d ** 2 * a % m
			else:
				d = d ** 2 % m
	else:
		s = bin(-b)[2:]
		(w, a, w) = rv(a, m)
		for j in s:
			if j == '1':
				d = d ** 2 * a % m
			else:
				d = d ** 2 % m
	print(d)


def fast_exp(x, n, m):
	r = 1
	while n:
		if n % 2:
			r = r * x % m
		x = x * x % m
		n //= 2
	return r

def xgcd(b, n):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return x0
for i in range(int(input())):
	(a, b, m) = map(int, input().split())
	if b == 0:
		print(1 % m)
	elif b < 0:
		print(fast_exp(xgcd(a, m), -b, m))
	else:
		print(fast_exp(a, b, m))


import sys

def egcd(a, b, x, y):
	if not a:
		return (0, 1)
	(l, m) = egcd(b % a, a, x, y)
	x = m - b // a * l
	y = l
	return (x, y)
T = int(sys.stdin.readline().strip())
for i in range(T):
	(x, y, z) = map(int, sys.stdin.readline().strip().split())
	inv = egcd(x, z, 0, 0)[0]
	inv_mod = inv if inv > 0 else inv + z
	output = pow(x, y, z) if y >= 0 else pow(inv_mod, abs(y), z)
	print(output)


P = []
for i in range(1000002):
	P.append([])
for i in range(2, 1000002):
	if P[i] == []:
		for j in range(1, 1000001 // i + 1):
			P[i * j] += [i]

def euler(m):
	temp = P[m]
	constant = m
	for i in range(len(temp)):
		constant = constant // temp[i] * (temp[i] - 1)
	return constant
for _ in range(int(input())):
	(A, B, X) = [int(a) for a in input().strip().split(' ')]
	if B >= 0:
		print(pow(A, B, X))
	else:
		B = -B
		B %= euler(X)
		A = pow(A, euler(X) - 1, X)
		print(pow(A, B, X))


def exGcd(a, b):
	if a == 0:
		return (0, 1)
	else:
		(y, x) = exGcd(b % a, a)
		return (x - b // a * y, y)

def modInv(a, m):
	(x, y) = exGcd(a, m)
	return x % m

def fstExp(a, n, m):
	re = 1
	while n > 0:
		if n & 1:
			re = re * a % m
		a = a * a % m
		n >>= 1
	return re
for _ in range(int(input())):
	(A, B, X) = [int(i) for i in input().split()]
	if B < 0:
		A = modInv(A, X)
	print(fstExp(A, abs(B), X))


def inv(n, p):
	(am, rm, a, r) = (1, n, 0, p)
	while r > 1:
		(am, rm, a, r) = (a, r, am - rm // r * a, rm % r)
	return a
T = int(input())
for run in range(T):
	(a, b, x) = [int(i) for i in input().split()]
	if b == 0:
		print(1 % x)
		continue
	if b < 0:
		a = inv(a, x)
		b = -1 * b
	p = 1
	while b > 0:
		if b % 2 == 1:
			p = p * a % x
		b //= 2
		a = a * a % x
	print(p)


import logging

def xgcd(b, n):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def fast_mod_power(A, B, X):
	logging.debug('computing %s ** %s %% %s', A, B, X)
	base = A
	factor = 1
	while B > 0:
		if B % 2 == 0:
			base *= base
			base %= X
			B //= 2
		else:
			factor *= base
			factor %= X
			B -= 1
	logging.debug('base %s, factor %s', base, factor)
	return factor % X
T = int(input())
for _ in range(T):
	(A, B, X) = (int(x) for x in input().split())
	if B < 0:
		(g, x, y) = xgcd(A, X)
		A = x
		B *= -1
	A %= X
	print(fast_mod_power(A, B, X))


from itertools import count
from functools import reduce
from fractions import Fraction
from operator import mul

def isPrime(x):
	if x <= 1:
		return False
	for i in Primes():
		if i * i > x:
			return True
		if x % i == 0:
			return False
known = [2, 3]

def Primes():
	for n in count(0):
		if n < len(known):
			yield known[n]
		elif n == len(known):
			x = known[-1] + 2
			while not isPrime(x):
				x += 2
			known.append(x)
			yield x
		else:
			raise IndexError('Primes() got ahead of itself')

def primeFactors(p):
	f = []
	for q in Primes():
		if p % q == 0:
			f.append(q)
			while p % q == 0:
				p //= q
		if p == 1:
			break
		if q * q > p:
			f.append(p)
			break
	return f

def phi(X):
	return int(X * reduce(mul, (1 - Fraction(1, q) for q in primeFactors(X))))
T = int(input())
for _ in range(T):
	(A, B, X) = map(int, input().split())
	if B < 0:
		B = -B * (phi(X) - 1)
	print(pow(A, B, X))


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if L == 0:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m

def is_prime(x, L):
	sqrt = int(pow(x, 0.5)) + 1
	p = 0
	while p < len(L) and L[p] <= sqrt:
		if not x % L[p]:
			return False
		p += 1
	return True

def euler_totient(x, L):
	totient = x
	if is_prime(x, L):
		return x - 1
	else:
		j = 0
		while j < len(L):
			if x % L[j] == 0:
				totient *= L[j] - 1
				totient //= L[j]
			j += 1
	return totient

def compute_primes(x):
	L = [2]
	for i in range(3, x // 2 + 1):
		divided = False
		j = 0
		sqrt = int(pow(i, 0.5)) + 1
		while j < len(L) and L[j] < sqrt and (not divided):
			if i % L[j] == 0:
				divided = True
			j += 1
		if not divided:
			L.append(i)
	return L
T = int(input())
prime_list = compute_primes(1000000)
for case in range(0, T):
	(a, b, x) = [int(r) for r in input().split()]
	if x > 1:
		if b < 0:
			et = euler_totient(x, prime_list)
			a_inverse = pow_mod(a, et - 1, x)
			print(pow_mod(a_inverse, -1 * b, x))
		elif b > 0:
			et = euler_totient(x, prime_list)
			print(pow_mod(a, b, x))
		else:
			print(1)
	else:
		print(1)


def euler(n):
	k = n
	Phi = 1
	Factors = []
	d1 = 5
	d2 = 7
	Turn = 1
	if not n % 2:
		Factors = Factors + [2]
		while not n % 2:
			n = n // 2
	if not n % 3:
		Factors = Factors + [3]
		while not n % 3:
			n = n // 3
	while n != 1:
		if Turn % 2:
			if not n % d1:
				Factors = Factors + [d1]
				while not n % d1:
					n = n // d1
			d1 += 6
			Turn += 1
		else:
			if not n % d2:
				Factors = Factors + [d2]
				while not n % d2:
					n = n // d2
			d2 += 6
			Turn += 1
	for a in Factors:
		Phi = Phi * (1 - 1 / a)
	return round(k * Phi, 0)

def powerOptimization(a, b, m):
	Total = 1
	i = 1
	Binary = []
	while b != 1:
		if not b % 2:
			b = b // 2
			Binary = [0] + Binary
		else:
			b = b // 2
			Binary = [1] + Binary
	if b == 1:
		Binary = [1] + Binary
	for x in Binary:
		if x == 1:
			ka = a
			for c in range(len(Binary) - i):
				ka = ka * ka % m
			Total = Total * ka
		i += 1
	return Total % X
T = eval(input())
for a in range(T):
	(A, B, X) = map(int, input().strip().split())
	if B > 0:
		sol = powerOptimization(A, B, X)
	elif B == 0:
		sol = 1
	else:
		k = powerOptimization(A, euler(X) - 1, X)
		sol = powerOptimization(k, -B, X)
	print(int(sol))


t = int(input())
for _ in range(t):
	(a, b, x) = map(int, input().split())
	if b >= 0:
		print(pow(a, b, x))
	else:
		i = 2
		res = x
		z = x
		while i * i <= x:
			if x % i == 0:
				while x % i == 0:
					x //= i
				res -= res // i
			i += 1
		if x > 1:
			res -= res // x
		print(pow(a, (res - 1) * abs(b), z))


def inverse(x, y):
	(z, w) = (x % y, x // y)
	if z == 1:
		return (1, -w)
	(l, r) = inverse(y, z)
	return (r, l - w * r)
t = int(input())
for i in range(t):
	(a, b, x) = list(map(int, input().split()))
	if b > 0:
		print(pow(a, b, x))
	else:
		print(pow(inverse(a, x)[0], -b, x))


def fastmod(a, b, x):
	ans = 1
	while b > 0:
		if b & 1:
			ans = ans * a % x
		b >>= 1
		a = a ** 2 % x
	return ans

def inverse(a, n):
	t = 0
	newt = 1
	r = n
	newr = a
	while newr != 0:
		quotient = r // newr
		(t, newt) = (newt, t - quotient * newt)
		(r, newr) = (newr, r - quotient * newr)
	if r > 1:
		return 'a is not invertible'
	if t < 0:
		t = t + n
	return t
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	if b < 0:
		a = inverse(a, x)
		b = -b
	print(fastmod(a, b, x))


from math import sqrt, gcd

def phi(n):
	f = primefactor(n)
	r = 1
	for p in f:
		r *= 1 - 1 / p
	return int(round(n * r, 0))

def firstfactor(N):
	l = int(sqrt(N)) + 1
	for i in range(2, l):
		if N % i == 0:
			return i
	return N

def primefactor(n):
	factors = {}
	while n != 1:
		f = firstfactor(n)
		n //= f
		if f in factors:
			factors[f] += 1
		else:
			factors[f] = 1
	return factors
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	if b >= 0:
		r = pow(a, b, x)
	else:
		ph = phi(x)
		inv = pow(a, ph - 1, x)
		r = pow(inv, -b, x)
	print(r)


def fastmodexp(a, b, c):
	res = 1
	while b != 0:
		if b % 2 == 0:
			a = a ** 2 % c
			b = b / 2
		else:
			res = res * a % c
			b -= 1
	return res

def modinv(a, p):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while p != 0:
		(q, a, p) = (a // p, p, a % p)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return x0
t = int(input(''))
for a0 in range(t):
	(a, b, x) = input().strip().split(' ')
	(a, b, x) = (int(a), int(b), int(x))
	if b >= 0:
		print(fastmodexp(a, b, x))
	else:
		print(fastmodexp(modinv(a, x), abs(b), x))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
T = int(input())
for _ in range(T):
	(A, B, X) = map(int, input().split())
	if B < 0:
		ainv = modinv(A, X)
		print(pow(ainv, -B, X))
	else:
		print(pow(A, B, X))


def modMultiInv(a, m):
	modsquared = m ** 2
	newa = a * m + 1
	while newa > m:
		t = modsquared % newa
		modsquared = newa
		newa = t
	return newa

def mult(x, y):
	return x * y % X

def exponentiationSq(A, n):
	if n == 0:
		return 1
	elif n == 1:
		return A
	elif n % 2 == 0:
		return exponentiationSq(mult(A, A), n / 2)
	elif n % 2 == 1:
		return mult(A, exponentiationSq(mult(A, A), (n - 1) / 2))
for i in range(int(input())):
	(A, B, X) = map(int, input().split())
	if B < 0:
		print(exponentiationSq(modMultiInv(A, X), abs(B)))
	else:
		print(exponentiationSq(A, B) % X)


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
t = int(input())
for i in range(t):
	(a, b, m) = [int(i) for i in input().split()]
	if b > 0:
		print(pow(a, b, m))
	elif b < 0:
		p = modInverse(a, m)
		print(pow(p, -b, m))
	else:
		print('1')


def mod_inv(a, n):
	(t, newt) = (0, 1)
	(r, newr) = (n, a)
	while newr != 0:
		quotient = r // newr
		(t, newt) = (newt, t - quotient * newt)
		(r, newr) = (newr, r - quotient * newr)
	if r > 1:
		return -1
	if t < 0:
		t = t + n
	return t
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	if b < 0:
		m = mod_inv(a, x)
		print(pow(m, -b, x))
	elif b == 0:
		print(1)
	else:
		print(pow(a, b, x))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def pow(a, x, m):
	rv = 1
	base = a
	while x > 0:
		if x % 2 == 1:
			rv = rv * base % m
		base = base * base % m
		x //= 2
	return rv

def epow(a, x, m):
	if x == 0:
		return 1
	if x < 0:
		ainv = modinv(a, m)
		return pow(ainv, -x, m)
	return pow(a, x, m)
num_q = int(input())
for _ in range(num_q):
	(a, x, m) = (int(x) for x in input().split())
	print(epow(a, x, m))


from math import ceil, sqrt

def phi(num):
	res = num
	for div in range(2, ceil(sqrt(num)) + 1):
		if num % div == 0:
			res *= div - 1
			res //= div
		while num % div == 0:
			num //= div
	if num > 1:
		res *= num - 1
		res //= num
	return res

def mod_pow(num, exp, mod):
	if exp == 0:
		return 1
	elif exp % 2 == 0:
		return mod_pow(num ** 2 % mod, exp // 2, mod)
	else:
		return num * mod_pow(num, exp - 1, mod) % mod

def mod_inv(num, mod):
	return mod_pow(num, phi(mod) - 1, mod)
T = int(input())
for t in range(T):
	(A, B, X) = map(int, input().split())
	if B >= 0:
		print(mod_pow(A, B, X))
	else:
		print(mod_pow(mod_inv(A, X), -B, X))


def inv(a, p):
	(k, l) = (1, 0)
	while p:
		(k, l) = (l, k - a // p * l)
		(a, p) = (p, a % p)
	return k
n = int(input())
for _ in range(n):
	(a, b, c) = tuple(map(int, input().split()))
	print(pow(a, b, c) if b >= 0 else pow(inv(a, c), -b, c))


def pow_mod(a, b, n):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans = ans * a % n
		b >>= 1
		a = a * a % n
	return ans

def extgcd(p, q):
	if q == 0:
		return (p, 1, 0)
	(r, x, y) = extgcd(q, p % q)
	tmp = y
	y = x - p // q * y
	x = tmp
	return (r, x, y)

def inv(a, n):
	(d, x, y) = extgcd(a, n)
	if d == 1:
		return (x + n) % n
	else:
		return -1
cases = int(input())
for i in range(cases):
	abx = input().split()
	a = int(abx[0])
	b = int(abx[1])
	x = int(abx[2])
	if b < 0:
		print(pow_mod(inv(a, x), -b, x))
	else:
		print(pow_mod(a, b, x))


def extended_euclid(a, b):
	t = 1
	r = b
	t_prev = 0
	r_prev = a
	while r != 0:
		q = r_prev // r
		(r, r_prev) = (r_prev - q * r, r)
		(t, t_prev) = (t_prev - q * t, t)
	return t_prev
t = int(input())
for i in range(t):
	vals = input()
	lst = vals.split(' ')
	a = int(lst[0])
	b = int(lst[1])
	x = int(lst[2])
	if b < 0:
		a = extended_euclid(x, a)
		b = b * -1
	bin_b = bin(b)[2:]
	bin_rev = bin_b[::-1]
	a_prev = a
	a_squares = [a]
	for j in range(1, len(bin_rev)):
		a_exp = a_prev ** 2
		a_prev = a_exp % x
		a_squares.append(a_prev)
	ans = 1
	for k in range(len(bin_rev)):
		if bin_rev[k] == '1':
			ans = a_squares[k] * ans % x
	print(ans)