module Main where
readInt :: IO Int
readInt = readLn
readIntegers :: IO [Integer]
readIntegers = fmap (map read.words) getLine
power a 0 n = mod 1 n
power a b n = let
x = power a (div b 2) n
y = mod (x*x) n
in if (mod b 2) == 0
then y
else mod (y*a) n
repea 0 = (putStrLn "")
repea t = do
[a, b, n] <- readIntegers
putStrLn $ show $ power a b n
repea (t - 1)
main = do
t <- readInt
repea t