DIV = 20

def ferma(x, y, n)

    c = 1

    for i in 0..y-1

        c = (c * x) % n

    end

    #p "[#{x}^#{y} mod #{n} = #{c}]"

    return c

end

def div_conq_ferma(x, y, n)

    #p "#{x}^#{y} mod #{n} = (#{x}^#{DIV})^#{y/DIV} * #{x}^#{y%DIV}, mod #{n}"

    mod1 = ferma(x, y % DIV, n)

    if (y > DIV)

        sub_mod0 = ferma(x, DIV, n)

        pwr_sub_mod0 = y / DIV

        mod0 = div_conq_ferma(sub_mod0, pwr_sub_mod0, n)

    else

        mod0 = 1

    end

    return ferma(mod1 * mod0, 1, n)

end

#

runcnt = gets.to_i

for i in 0..runcnt-1

    str = gets.split

    x = str[0].to_i

    y = str[1].to_i

    n = str[2].to_i

    p div_conq_ferma(x, y, n)

end