using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;

public static class P
{
    public static void Main()
    {
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
     
        string line;
        
        line = Console.ReadLine();
        //Assert(Regex.IsMatch(line, @"^\d+$"));
        var t = int.Parse(line);

        //Assert(1 <= t && t <= 1000);

        for (int i = 0; i < t; i++)
        {
            line = Console.ReadLine();
            //Assert(Regex.IsMatch(line, @"^\d+ \d+ \d+$"));

            var pka = line.Split().Select(int.Parse).ToArray();
            var p = pka[0];
            var k = pka[1];
            var a = pka[2];

            //Assert(2 <= k && k <= 1000);
            //Assert(2 <= p && p <= 1000000007);
            //Assert(1 <= a && a < p);

            Solve(p, k, a);
        }

        Console.Out.Flush();
    }

    static void Solve(int p, int k, int a)
    {
        ModInt.Mod = p;

        var step = GCD(k, p - 1);
        if (Power(a, (p - 1) / step) != 1) { Console.WriteLine(-1); return; }


        //有限体Z/pZの原始根gを一つ求め、
        var g = GetPrimitiveRoot(p);
        //そのgについてのaの指数を求める。
        var aIndex = Log(a, g);
        //これによって、Z/(p-1)Z上でのa/kを求める問題に帰着できる
        //∵x^k≡a(mod p) ⇔ (g^xInd)^k≡(g^aInd)(mod p) ⇔ (xInd)*k≡aInd(mod p-1)
        //x=a/kとすると、kx=aより、aはZ/(p-1)Z上でik(i∈ℕ)と等しい必要がある。
        //これは、Z/(p-1)Z上において指数がgcd(k, p - 1)で割り切れる要素のみで構成される群の要素と等しい。
        //よって、stepを生成元として(p-1)を法とする加法によって生成される巡回群の位数orderは、
        var order = (p - 1) / step;

        //まず、aがその巡回群に乗っていない場合、除算は不可能。

        //Z/orderZ上でのa,kの指数はそれぞれ、
        var aIndexOnZOrderZ = aIndex / step;
        var kIndexOnZOrderZ = k / step;

        //ここで、Z/orderZ上でのa/k=xの指数は、
        var xIndex = (aIndexOnZOrderZ * GetInverse(kIndexOnZOrderZ, order)) % order;
        //Z/orderZはZ/(p-1)Zの部分群なので、Z/(p-1)Zにおいても指数は等しい。よって、
        Console.WriteLine(Power(g, xIndex));
    }
	
	static bool isPrimitiveRoot(long a,long p){
		bool ret=true;
		for(long div=2;div*div<=p-1;++div){
			ret&=pow(a,div,p)!=1;
			ret&=pow(a,(p-1)/div,p)!=1;
			if(!ret)return false;
		}
		return true;
	}
	
	static long pow(long a,long n,long p){
		n%=p-1;
		long r=1;
		for(;n>0;n>>=1,a=a*a%p)if(n%2==1)r=r*a%p;
		return r;
	}	
    static long GetPrimitiveRoot(long p)
    {
		for(long i=1;i<p;++i){
			if(isPrimitiveRoot(i,p))return i;
		}
        throw new Exception();
    }

    static int Log(ModInt a, ModInt b)
    {
        const int PACKET_SIZE = 65536;
        ModInt currentInv = 1;
        Dictionary<ModInt, int> babySteps = new Dictionary<ModInt, int>();
        for (int i = 0; i < PACKET_SIZE; i++)
        {
            if (babySteps.ContainsKey(currentInv))
            {
                if (babySteps.ContainsKey(a)) return babySteps[a];
                else return -1;
            }
            babySteps.Add(currentInv, i);
            currentInv *= b;
        }
        ModInt singleGiantStepInv = currentInv;
        currentInv = 1;
        for (int i = 0; i < ModInt.Mod; i += PACKET_SIZE)
        {
            var babyStep = a * currentInv;
            if (babySteps.ContainsKey(babyStep)) return i + babySteps[babyStep];
            currentInv *= singleGiantStepInv;
        }
        return -1;
    }

    static ModInt Power(ModInt n, long m)
    {
        ModInt pow = n;
        ModInt res = 1;
        while (m > 0)
        {
            if ((m & 1) == 1) res *= pow;
            pow *= pow;
            m >>= 1;
        }
        return res;
    }

    static void Assert(bool cond)
    {
        if (!cond) throw new Exception();
    }


    static long GCD(long a, long b)
    {
		return a == 0 ? b : GCD(b % a, a);
    }

    static long GetInverse(long a, long MOD)
    {
        long div, p = MOD, x1 = 1, y1 = 0, x2 = 0, y2 = 1;
        while (true)
        {
            if (p == 1) return x2 + MOD; div = a / p; x1 -= x2 * div; y1 -= y2 * div; a %= p;
            if (a == 1) return x1 + MOD; div = p / a; x2 -= x1 * div; y2 -= y1 * div; p %= a;
        }
    }
}



struct ModInt
{
    public static int Mod
    {
        get
        {
            return MOD;
        }
        set
        {
            MOD = value;
            POSITIVIZER = (long)MOD << 31;
        }
    }
    static int MOD = 1000000007;
    static long POSITIVIZER = ((long)MOD) << 31;
    long Data;
    public ModInt(long data) { if ((Data = data % MOD) < 0) Data += MOD; }
    public static implicit operator long(ModInt modInt) => modInt.Data;
    public static implicit operator ModInt(long val) => new ModInt(val);
    public static ModInt operator +(ModInt a, int b) => new ModInt() { Data = (a.Data + b + POSITIVIZER) % MOD };
    public static ModInt operator +(ModInt a, long b) => new ModInt(a.Data + b);
    public static ModInt operator +(ModInt a, ModInt b) { long res = a.Data + b.Data; return new ModInt() { Data = res >= MOD ? res - MOD : res }; }
    public static ModInt operator -(ModInt a, int b) => new ModInt() { Data = (a.Data - b + POSITIVIZER) % MOD };
    public static ModInt operator -(ModInt a, long b) => new ModInt(a.Data - b);
    public static ModInt operator -(ModInt a, ModInt b) { long res = a.Data - b.Data; return new ModInt() { Data = res < 0 ? res + MOD : res }; }
    public static ModInt operator *(ModInt a, int b) => new ModInt(a.Data * b);
    public static ModInt operator *(ModInt a, long b) => a * new ModInt(b);
    public static ModInt operator *(ModInt a, ModInt b) => new ModInt() { Data = a.Data * b.Data % MOD };
    public static ModInt operator /(ModInt a, ModInt b) => new ModInt() { Data = a.Data * GetInverse(b) % MOD };
    public override string ToString() => Data.ToString();
    static long GetInverse(long a)
    {
        long div, p = MOD, x1 = 1, y1 = 0, x2 = 0, y2 = 1;
        while (true)
        {
            if (p == 1) return x2 + MOD; div = a / p; x1 -= x2 * div; y1 -= y2 * div; a %= p;
            if (a == 1) return x1 + MOD; div = p / a; x2 -= x1 * div; y2 -= y1 * div; p %= a;
        }
    }
    public override bool Equals(object obj) => ((ModInt)obj).Data == Data;
    public override int GetHashCode() => (int)Data;
}