Implement pow(x, n) % M.
In other words, given x, n and M, find (x^{n}) % M.
 
Example 1:
Input:
x = 3, n = 2, m = 4
Output:
1
Explanation:
3^{2} = 9. 9 % 4 = 1.
Example 2:
Input:
x = 2, n = 6, m = 10
Output:
4
Explanation:
2^{6} = 64. 64 % 10 = 4.
Your Task:
You don't need to read or print anything. Your task is to complete the function PowMod() which takes integers x, n and M as input parameters and returns x^{n} % M.
 
Expected Time Complexity: O(log(n))
Expected Space Complexity: O(1)
 
Constraints:
1 ≤ x, n, M ≤ 10^{9}

Difficulty: MEDIUM
Tags: Sorting

Divide and conquer
Skill types: Sorting
Expected Time Complexity: O(log(n))
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

	def PowMod(self, x, n, m):

		# Code here

Solutions:
class Solution:

	def PowMod(self, x, n, m):
		res = 1
		while n > 0:
			if n & 1 != 0:
				res = res * x % m % m
			x = x % m * x % m % m
			n = n >> 1
		return res


class Solution:

	def PowMod(self, x, n, m):
		result = 1
		while n > 0:
			if n % 2 == 1:
				result = result * x % m
			x = x * x % m
			n //= 2
		return result


class Solution:

	def PowMod(self, x, n, m):
		res = 1
		if n == 1:
			return x
		if n % 2 != 0:
			res = x * self.PowMod(x, n - 1, m)
			return res % m
		else:
			con = self.PowMod(x, n // 2, m)
			con *= con
			return con % m


class Solution:

	def PowMod(self, x, n, m):

		def power(x, n, m):
			if n == 1:
				return x % m
			elif n % 2 == 0:
				y = power(x, n / 2, m)
				return y * y % m
			else:
				y = power(x, (n - 1) / 2, m)
				return y * y * x % m
		return power(x, n, m)


class Solution:

	def PowMod(self, x, n, m):
		return pow(x, n, m)


class Solution:

	def PowMod(self, x, n, m):
		dp = [0 for _ in range(32)]
		dp[0] = x % m
		for i in range(1, 32):
			dp[i] = dp[i - 1] * dp[i - 1] % m
		res = 1
		k = 0
		while n > 0:
			i = n & -n
			j = 0
			l = 0
			while i > 0:
				i >>= 1
				j += 1
			res *= dp[j - 1]
			res %= m
			n &= n - 1
		return res


class Solution:

	def PowMod(self, x, n, m):

		def power(x, n, m):
			if n == 0:
				return 1
			else:
				ans = power(x, n // 2, m)
				if n % 2 == 0:
					return ans * ans % m
				else:
					return ans * ans * x % m
		ans = power(x, n, m)
		return ans


class Solution:

	def PowMod(self, x, n, m):
		if n == 0:
			return 1
		temp = self.PowMod(x, n // 2, m)
		temp = temp * temp % m
		if n % 2 == 0:
			return temp % m
		else:
			return x * temp % m


class Solution:

	def PowMod(self, x, n, M):
		ans = 1
		while n > 0:
			if n & 1:
				ans = ans * x % M
			x = x * x % M
			n >>= 1
		return ans % M


class Solution:

	def PowMod(self, x, n, m):
		a = 1
		x = x % m
		while n > 1:
			if n % 2:
				a = a * x % m
				n = (n - 1) // 2
			else:
				n = n // 2
			x = x ** 2 % m
		return x * a % m


class Solution:

	def PowMod(self, x, n, m):

		def solve(x, n, m):
			if n == 0:
				return 1
			elif n == 1:
				return x % m
			temp = solve(x, n // 2, m)
			if n % 2 == 0:
				return temp * temp % m
			return temp * temp * x % m
		return solve(x, n, m)


class Solution:

	def PowMod(self, x, n, m):
		if not n:
			return 1
		if n == 1:
			return x % m
		if n % 2:
			return x % m * self.PowMod(x % m * x % m % m, (n - 1) // 2, m) % m % m
		return self.PowMod(x % m * x % m % m, n // 2, m) % m


from functools import lru_cache

class Solution:

	def PowMod(self, x, n, m):

		@lru_cache()
		def make(i):
			if i == 1:
				return x % m
			a = 1 if i % 2 == 0 else x % m
			return make(i // 2) ** 2 * a % m
		return make(n)


class Solution:

	def PowMod(self, x, n, m):
		res = 1
		while n:
			rem = n & 1
			if rem % 2:
				res = res % m * x % m % m
			x = x % m * x % m % m
			n >>= 1
		return res % m


class Solution:

	def PowMod(self, x, n, m):
		t = 1
		while n > 0:
			if n % 2 != 0:
				t = t * x
			x = x * x % m
			n = int(n / 2)
		return t % m


class Solution:

	def PowMod(self, x, n, m):
		if n == 1:
			return x % m
		elif n % 2:
			return x % m * self.PowMod(x, n - 1, m) % m
		else:
			ans = self.PowMod(x, n // 2, m) % m
			return ans * ans % m


class Solution:

	def powModUtils(self, x, n, m):
		if n <= 1:
			return x
		n_rem = n % 2
		res = self.powModUtils(x, n // 2, m)
		return res * res * x % m if n_rem > 0 else res * res % m

	def PowMod(self, x, n, m):
		return self.powModUtils(x, n, m)


class Solution:

	def modexp(self, n):
		if n == 0:
			return 1
		isodd = n & 1
		n >>= 1
		z = self.modexp(n)
		if isodd:
			return self.x * z * z % self.m
		else:
			return z * z % self.m

	def PowMod(self, x, n, m):
		self.x = x
		self.m = m
		return self.modexp(n)


class Solution:

	def PowMod(self, x, n, m):
		if n == 0:
			return 1
		elif n % 2 == 0:
			a = self.PowMod(x, n // 2, m) % m
			return a * a % m
		else:
			a = self.PowMod(x, n // 2, m) % m
			num = x % m
			return x * a * a % m


class Solution:

	def PowMod(self, x, y, p):
		res = 1
		x = x % p
		if x == 0:
			return 0
		while y > 0:
			if y & 1 == 1:
				res = res * x % p
			y = y >> 1
			x = x * x % p
		return res


class Solution:

	def PowMod(self, a, n, m):
		a %= m
		if a == 0:
			return 0
		(res, power) = (1, a)
		while n > 0:
			if n & 1 == 1:
				res *= power
				res %= m
			power = power * power % m
			n = n >> 1
		res %= m
		return res


class Solution:

	def PowMod(self, x, n, m):
		l = [x]
		c = 1
		while c < n:
			d = l[-1] * l[-1]
			l.append(d % m)
			c = c * 2
		s = bin(n)
		s = s[2:]
		s = s[::-1]
		p = 1
		d = 0
		for i in s:
			if i == '1':
				p = p * l[d]
			p = p % m
			d += 1
		return p


class Solution:

	def __init__(self):
		self.count = 0

	def PowMod(self, x, n, m):
		if n == 0:
			return 1
		elif n > 0:
			if n % 2 == 0:
				self.count += 1
				d = self.PowMod(x, n // 2, m)
				return d * d % m
			else:
				return x * self.PowMod(x, n - 1, m) % m
		else:
			n = -n
			if n % 2 == 0:
				d = self.PowMod(x, n // 2, m)
				return 1 / (d * d) % m
			else:
				return 1 / (x * self.PowMod(x, n - 1, m)) % m


class Solution:

	def recurse(self, x, n, m):
		if n == 0:
			return 1
		nby2 = n // 2
		xnby2 = self.recurse(x, nby2, m)
		if n % 2 == 0:
			return xnby2 % m * xnby2 % m % m
		else:
			return x * xnby2 % m * (xnby2 % m) % m

	def PowMod(self, x, n, m):
		if x == 1:
			return 1
		x = x % m
		return self.recurse(x, n, m)


class Solution:

	def PowMod(self, x, n, m):
		c = pow(x, n, m)
		return int(c)


class Solution:

	def PowMod(self, a, b, mod):
		res = 1
		while b > 0:
			if b & 1 != 0:
				res = res * a
			res %= mod
			b = b >> 1
			a = a * a
			a %= mod
		return res % mod


import math

class Solution:

	def PowMod(self, x, n, m):
		r = 1
		while n:
			if n % 2 == 0:
				x = x % m * x % m % m
			else:
				r = r % m * x % m % m
				x = x % m * x % m % m
				r %= m
			n = n // 2
		return r % m


class Solution:

	def PowMod(self, x, y, p):
		res = 1
		x = x % p
		if x == 0:
			return 0
		while y > 0:
			if y & 1 == 1:
				res = res * x % p
			y = y >> 1
			x = x * x % p
		return res % m
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(x, n, m) = input().split()
		x = int(x)
		n = int(n)
		m = int(m)
		ob = Solution()
		ans = ob.PowMod(x, n, m)
		print(ans)


class Solution:

	def PowMod(self, base, power, M):
		ans = 1
		while power:
			if power & 1:
				ans = ans * base
				ans %= M
			base = base * base % M
			power >>= 1
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(x, n, m) = input().split()
		x = int(x)
		n = int(n)
		m = int(m)
		ob = Solution()
		ans = ob.PowMod(x, n, m)
		print(ans)


class Solution:

	def PowMod(self, x, n, m):

		def solve(x, n):
			if n == 0:
				return 1
			res = solve(x, n // 2)
			if n & 1:
				return x * (res * res) % m % m
			else:
				return res * res % m
		return solve(x, n)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(x, n, m) = input().split()
		x = int(x)
		n = int(n)
		m = int(m)
		ob = Solution()
		ans = ob.PowMod(x, n, m)
		print(ans)


class Solution:

	def PowMod(self, A, B, C):
		if A == 0:
			return 0
		if B == 0:
			return 1
		y = 0
		if B % 2 == 0:
			y = self.PowMod(A, B / 2, C)
			y = y * y % C
		else:
			y = A % C
			y = y * self.PowMod(A, B - 1, C) % C % C
		return (y + C) % C


class Solution:

	def PowMod(self, x, n, m):
		if n == 0:
			return 1 % m
		if n == 1:
			return x % m
		if n > 0:
			power = pow(x, n, m)
		if n < 0:
			power = pow(x, n, m)
		return power

def calc(n, x):
	ans = 1
	while n != 1:
		if n % 2 == 0:
			n = n / 2
			x *= x
		else:
			n = n - 1
			ans *= x
	ans *= x
	return ans


class Solution:

	def PowMod(self, g, k, p):
		y = 1
		bin_k = bin(k)[2:]
		for i in range(0, len(bin_k)):
			ki = int(bin_k[i])
			if ki == 1:
				y = y ** 2 % p * g % p
			else:
				y = y ** 2 % p
		return y


class Solution:

	def PowMod(self, x, n, m):

		def check(x, n, m):
			if n == 0:
				return 1
			res = check(x, n // 2, m)
			if n % 2 == 0:
				return res % m * (res % m) % m
			else:
				return x % m * (res % m) * (res % m) % m
		m1 = check(x, n, m)
		return m1 % m


class Solution:

	def PowMod(self, x, n, m):
		x %= m
		ans = 1
		while n:
			if n & 1:
				ans *= x
				ans %= m
			n >>= 1
			x *= x
			x %= m
		return ans % m


class Solution:

	def PowMod(self, x, n, m):
		if n == 0:
			return 1
		if n % 2 == 0:
			y = self.PowMod(x, n / 2, m) % m
			return y * y % m
		return x % m * self.PowMod(x, n - 1, m) % m