// Bundled at 2026/07/13 19:37:14 +09:00
// Author: Haar

pub mod main {
    use super::*;
    #[allow(unused_imports)]
    use haar_lib::{get, input, io::fastio::*, iter::join_str::*, output};
    #[allow(unused_imports)]
    use std::cell::{Cell, RefCell};
    #[allow(unused_imports)]
    use std::cmp::{max, min, Reverse};
    #[allow(unused_imports)]
    use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
    #[allow(unused_imports)]
    use std::io::Write;
    #[allow(unused_imports)]
    use std::mem::swap;
    #[allow(unused_imports)]
    use std::rc::Rc;
    pub struct Problem {
        io: FastIO,
    }
    use haar_lib::math::mod_ops::root::*;
    impl Problem {
        pub fn init() -> Self {
            Self { io: FastIO::new() }
        }
        pub fn main(&mut self) {
            let t = self.io.read_usize();
            for _ in 0..t {
                let p = self.io.read_u64();
                let k = self.io.read_u64();
                let a = self.io.read_u64();
                let ans = mod_kth_root(a, k, p);
                if let Some(ans) = ans {
                    self.io.writeln(ans);
                } else {
                    self.io.writeln(-1);
                }
            }
        }
    }
}
fn main() {
    std::thread::Builder::new()
        .spawn(|| main::Problem::init().main())
        .unwrap()
        .join()
        .unwrap()
}
use crate as haar_lib;
pub mod io {
    pub mod fastio {
        use std::fmt::Display;
        use std::io::{Read, Write};
        pub struct FastIO {
            in_bytes: Vec<u8>,
            in_cur: usize,
            out_buf: std::io::BufWriter<std::io::Stdout>,
        }
        impl FastIO {
            pub fn new() -> Self {
                let mut s = vec![];
                std::io::stdin().read_to_end(&mut s).unwrap();
                let cout = std::io::stdout();
                Self {
                    in_bytes: s,
                    in_cur: 0,
                    out_buf: std::io::BufWriter::new(cout),
                }
            }
            #[inline]
            pub fn getc(&mut self) -> Option<u8> {
                let c = *self.in_bytes.get(self.in_cur)?;
                self.in_cur += 1;
                Some(c)
            }
            #[inline]
            pub fn peek(&self) -> Option<u8> {
                Some(*self.in_bytes.get(self.in_cur)?)
            }
            #[inline]
            pub fn skip(&mut self) {
                while self.peek().is_some_and(|c| c.is_ascii_whitespace()) {
                    self.in_cur += 1;
                }
            }
            pub fn read_u64(&mut self) -> u64 {
                self.skip();
                let mut ret: u64 = 0;
                while self.peek().is_some_and(|c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
                    self.in_cur += 1;
                }
                ret
            }
            pub fn read_u32(&mut self) -> u32 {
                self.read_u64() as u32
            }
            pub fn read_usize(&mut self) -> usize {
                self.read_u64() as usize
            }
            pub fn read_i64(&mut self) -> i64 {
                self.skip();
                let mut ret: i64 = 0;
                let minus = if self.peek() == Some(b'-') {
                    self.in_cur += 1;
                    true
                } else {
                    false
                };
                while self.peek().is_some_and(|c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
                    self.in_cur += 1;
                }
                if minus {
                    ret = -ret;
                }
                ret
            }
            pub fn read_i32(&mut self) -> i32 {
                self.read_i64() as i32
            }
            pub fn read_isize(&mut self) -> isize {
                self.read_i64() as isize
            }
            pub fn read_f64(&mut self) -> f64 {
                self.read_chars()
                    .into_iter()
                    .collect::<String>()
                    .parse()
                    .unwrap()
            }
            pub fn read_chars(&mut self) -> Vec<char> {
                self.read_bytes().into_iter().map(Into::into).collect()
            }
            pub fn read_string(&mut self) -> String {
                self.read_chars().into_iter().collect()
            }
            pub fn read_bytes(&mut self) -> Vec<u8> {
                self.skip();
                let mut ret = vec![];
                while self.peek().is_some_and(|c| c.is_ascii_graphic()) {
                    ret.push(self.in_bytes[self.in_cur]);
                    self.in_cur += 1;
                }
                ret
            }
            pub fn read_char(&mut self) -> char {
                self.skip();
                self.getc().unwrap().into()
            }
            pub fn writeln_u32(&mut self, mut n: u32) {
                if n == 0 {
                    self.out_buf.write_all(b"0\n").unwrap();
                    return;
                }
                let mut buf = [b' '; 10];
                let mut i = 9;
                while n > 0 {
                    buf[i] = (n % 10) as u8 + b'0';
                    n /= 10;
                    i -= 1;
                }
                self.out_buf.write_all(&buf).unwrap();
                self.out_buf.write_all(b"\n").unwrap();
            }
            pub fn write<T: Display>(&mut self, s: T) {
                self.out_buf.write_all(s.to_string().as_bytes()).unwrap();
            }
            pub fn write_rev<T: Display>(&mut self, s: T) {
                let mut s = s.to_string().as_bytes().to_vec();
                s.reverse();
                self.out_buf.write_all(&s).unwrap();
            }
            pub fn writeln<T: Display>(&mut self, s: T) {
                self.write(s);
                self.out_buf.write_all(b"\n").unwrap();
            }
            pub fn writeln_rev<T: Display>(&mut self, s: T) {
                self.write_rev(s);
                self.out_buf.write_all(b"\n").unwrap();
            }
            pub fn write_bytes(&mut self, s: &[u8]) {
                self.out_buf.write_all(s).unwrap();
            }
            pub fn writeln_intersperse<I>(&mut self, it: I)
            where
                I: IntoIterator,
                I::Item: Display,
            {
                let mut it = it.into_iter();
                if let Some(s) = it.next() {
                    self.write(s);
                }
                for s in it {
                    self.write_bytes(b" ");
                    self.write(s);
                }
                self.write_bytes(b"\n");
            }
        }
        impl Drop for FastIO {
            fn drop(&mut self) {
                self.out_buf.flush().unwrap();
            }
        }
    }
}
pub mod iter {
    pub mod join_str {
        pub trait JoinStr: Iterator {
            fn join_str(self, s: &str) -> String
            where
                Self: Sized,
                Self::Item: ToString,
            {
                self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
            }
        }
        impl<I> JoinStr for I where I: Iterator + ?Sized {}
    }
}
pub mod macros {
    pub mod io {
        #[macro_export]
        macro_rules! get {
    ( $in:expr; [$a:tt $(as $to:ty)*; $num:expr] ) => {
        (0..$num).map(|_| get!($in; $a $(as $to)*)).collect::<Vec<_>>()
    };
    ( $in:expr; ($($type:tt $(as $to:ty)*),*) ) => {
        ($(get!($in; $type $(as $to)*)),*)
    };
    ( $in:expr; i8 ) => { $in.read_i64() as i8 };
    ( $in:expr; i16 ) => { $in.read_i64() as i16 };
    ( $in:expr; i32 ) => { $in.read_i64() as i32 };
    ( $in:expr; i64 ) => { $in.read_i64() };
    ( $in:expr; isize ) => { $in.read_i64() as isize };
    ( $in:expr; u8 ) => { $in.read_u64() as u8 };
    ( $in:expr; u16 ) => { $in.read_u64() as u16 };
    ( $in:expr; u32 ) => { $in.read_u64() as u32 };
    ( $in:expr; u64 ) => { $in.read_u64() };
    ( $in:expr; usize ) => { $in.read_u64() as usize };
    ( $in:expr; char) => { $in.read_char() };
    ( $in:expr; [u8]) => { $in.read_bytes() };
    ( $in:expr; [char] ) => { $in.read_chars() };
    ( $in:expr; String ) => { $in.read_string() };
    ( $in:expr; $from:tt as $to:ty ) => { <$to>::from(get!($in; $from)) };
}
        #[macro_export]
        macro_rules! input {
    ( @inner $in:expr, $name:pat, $type:tt ) => {
        let $name = get!($in; $type);
    };
    ( @inner $in:expr, $name:pat, $type:tt as $to:ty ) => {
        let $name = get!($in; $type as $to);
    };
    ( $in:expr; $( $names:pat = $type:tt $(as $to:ty)? ),* ) => {
        $(input!(@inner $in, $names, $type $(as $to)?);)*
    }
}
        #[macro_export]
        macro_rules! output {
    ( @one $io:expr, $a:expr ) => {
        $io.write($a);
    };
    ( $io:expr; $a:expr, $($rest:expr),* ) => {
        output!(@one $io, $a);
        $(
            $io.write(" ");
            $io.write($rest);
        )*
        $io.writeln("");
    };
}
    }
}
pub mod math {
    pub mod factorize {
        pub mod pollard_rho {
            use crate::math::{gcd_lcm::*, montgomery::*, primality::miller_rabin::*};
            fn find_factor(n: u64, a: u64) -> Option<u64> {
                assert!(n % 2 == 1);
                let mn = Montgomery::new(n);
                let f = |x| mn.add(mn.mul(x, x), Wrapped(a));
                let mut x = mn.wrap(a);
                let mut y = f(x);
                loop {
                    x = f(x);
                    y = f(f(y));
                    let x = mn.unwrap(x);
                    let y = mn.unwrap(y);
                    let d = x.abs_diff(y).gcd(n);
                    if d == 1 {
                        continue;
                    }
                    return (d < n).then_some(d);
                }
            }
            pub fn pollard_rho(mut n: u64) -> Vec<u64> {
                assert!(n > 0);
                if n == 1 {
                    return vec![];
                }
                let mut ret = vec![];
                while n % 2 == 0 {
                    ret.push(2);
                    n /= 2;
                }
                let mut remain = vec![n];
                while let Some(n) = remain.pop() {
                    if n == 1 {
                        continue;
                    }
                    if MillerRabin.is_prime(n) {
                        ret.push(n);
                        continue;
                    }
                    if let Some(p) = (1..).find_map(|a| find_factor(n, a)) {
                        remain.push(n / p);
                        remain.push(p);
                    }
                }
                ret.sort();
                ret
            }
        }
    }
    pub mod gcd_lcm {
        use std::mem::swap;
        pub trait GcdLcm {
            type Output;
            fn gcd(self, _: Self::Output) -> Self::Output;
            fn lcm(self, _: Self::Output) -> Self::Output;
            fn gcd_lcm(self, _: Self::Output) -> (Self::Output, Self::Output);
        }
        macro_rules! gcd_lcm_impl_all {
    ( $($t:ty),* ) => {
        $(
            impl GcdLcm for $t {
                type Output = $t;
                fn gcd(self, mut b: Self::Output) -> Self::Output {
                    let mut a = self;
                    if a < b {
                        swap(&mut a, &mut b);
                    }
                    if b == 0 {
                        return a;
                    }
                    b.gcd(a % b)
                }
                fn lcm(self, b: Self::Output) -> Self::Output {
                    self / self.gcd(b) * b
                }
                fn gcd_lcm(self, b: Self::Output) -> (Self::Output, Self::Output) {
                    let g = self.gcd(b);
                    (g, self / g * b)
                }
            }
        )*
    }
}
        gcd_lcm_impl_all!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
    }
    pub mod mod_ops {
        pub mod inv {
            use crate::math::gcd_lcm::GcdLcm;
            pub fn mod_inv(mut a: u64, m: u64) -> Option<u64> {
                assert!(
                    0 < m && m <= 0xFFFFFFFF,
                    "Violated 0 < m <= 0xFFFFFFFF (m = {m})"
                );
                if a >= m {
                    a %= m;
                }
                if a.gcd(m) != 1 {
                    return None;
                }
                let mut b = m;
                let mut u = 1;
                let mut v = 0;
                while b > 0 {
                    let t = a / b;
                    a -= t * b;
                    (a, b) = (b, a);
                    if u < t * v {
                        u += m - (t * v) % m;
                        if u >= m {
                            u -= m;
                        }
                    } else {
                        u -= t * v;
                    }
                    (u, v) = (v, u);
                }
                Some(u)
            }
        }
        pub mod log {
            use crate::math::{
                gcd_lcm::GcdLcm,
                mod_ops::{inv::*, pow::*},
            };
            use std::collections::HashMap;
            pub fn mod_log(a: u64, mut b: u64, mut m: u64) -> Option<u64> {
                assert!(
                    0 < m && m <= 0xFFFFFFFF,
                    "Violated 0 < m <= 0xFFFFFFFF (m = {m})"
                );
                if b >= m {
                    b %= m;
                }
                if b == 1 {
                    return Some(0);
                }
                let mut d = 0;
                loop {
                    let g = a.gcd(m);
                    if g != 1 {
                        if b % g != 0 {
                            return None;
                        }
                        d += 1;
                        m /= g;
                        b /= g;
                        b *= mod_inv(a / g, m).unwrap();
                        b %= m;
                        if b == 1 {
                            return Some(d);
                        }
                    } else {
                        break;
                    }
                }
                let sq = (m as f64).sqrt() as u64 + 1;
                let mut mp = HashMap::new();
                let mut t = 1 % m;
                for i in 0..sq {
                    mp.entry(t).or_insert(i);
                    t *= a;
                    t %= m;
                }
                let x = mod_pow(mod_inv(a, m).unwrap(), sq, m);
                let mut t = b % m;
                for i in 0..sq {
                    if let Some(k) = mp.get(&t) {
                        return Some(i * sq + k + d);
                    }
                    t *= x;
                    t %= m;
                }
                None
            }
        }
        pub mod pow {
            #[inline]
            pub const fn mod_pow(mut x: u64, mut p: u64, m: u64) -> u64 {
                assert!(0 < m && m <= 0xFFFFFFFF, "Violated 0 < m <= 0xFFFFFFFF");
                if x >= m {
                    x %= m;
                }
                let mut ret = 1;
                while p > 0 {
                    if (p & 1) != 0 {
                        ret = (ret * x) % m;
                    }
                    x = (x * x) % m;
                    p >>= 1;
                }
                ret
            }
        }
        pub mod root {
            use crate::math::{
                gcd_lcm::GcdLcm,
                mod_ops::{inv::mod_inv, log::mod_log, pow::mod_pow},
                primitive_root_u64::primitive_root_u64,
            };
            pub fn mod_kth_root(a: u64, k: u64, p: u64) -> Option<u64> {
                let g = primitive_root_u64(p);
                let y = mod_log(g, a, p)?;
                let yg = y.gcd(p - 1);
                let kg = k.gcd(p - 1);
                if !yg.is_multiple_of(kg) {
                    return None;
                }
                let k_ = k / kg;
                let y_ = y / kg;
                let p_ = (p - 1) / kg;
                let z = y_ * mod_inv(k_, p_).unwrap() % p_;
                let x = mod_pow(g, z, p);
                assert_eq!(mod_pow(x, k, p), a % p);
                Some(x)
            }
        }
    }
    pub mod primality {
        pub mod miller_rabin {
            use crate::math::montgomery::*;
            pub use crate::math::primality::PrimalityTest;
            fn is_composite(a: u64, s: u32, d: u64, mg: Montgomery) -> bool {
                let a = mg.wrap(a);
                let pp = mg.wrap(mg.modulo() - 1);
                let mut x = mg.pow(a, d);
                if mg.unwrap(x) == 1 {
                    false
                } else {
                    for _ in 0..s {
                        if x == pp {
                            return false;
                        }
                        x = mg.mul(x, x);
                    }
                    true
                }
            }
            pub struct MillerRabin;
            impl PrimalityTest<u64> for MillerRabin {
                fn is_prime(&self, n: u64) -> bool {
                    if n <= 1 {
                        false
                    } else if n == 2 {
                        true
                    } else if n % 2 == 0 {
                        false
                    } else {
                        let s = (n - 1).trailing_zeros();
                        let d = (n - 1) >> s;
                        let mg = Montgomery::new(n);
                        if n < 4_759_123_141 {
                            ![2, 7, 61]
                                .into_iter()
                                .any(|a| a < n && is_composite(a, s, d, mg))
                        } else {
                            ![2, 325, 9375, 28178, 450775, 9780504, 1795265022]
                                .into_iter()
                                .any(|a| a < n && is_composite(a, s, d, mg))
                        }
                    }
                }
            }
        }
        pub trait PrimalityTest<T> {
            fn is_prime(&self, value: T) -> bool;
        }
    }
    pub mod primitive_root_u64 {
        use crate::math::{factorize::pollard_rho::*, montgomery::*, primality::miller_rabin::*};
        pub fn primitive_root_u64(p: u64) -> u64 {
            if p == 2 {
                return 1;
            }
            assert!(MillerRabin.is_prime(p), "{p} is not a prime number.");
            let pf = pollard_rho(p - 1);
            let mn = Montgomery::new(p);
            (2..p)
                .find(|&g| {
                    pf.iter()
                        .all(|f| mn.unwrap(mn.pow(mn.wrap(g), (p - 1) / f)) != 1)
                })
                .expect("No primitive roots.")
        }
    }
    pub mod montgomery {
        const B: u32 = 64;
        const R: u128 = 1 << B;
        const MASK: u128 = R - 1;
        #[derive(Clone, Copy)]
        pub struct Montgomery {
            modulo: u64,
            r2: u128,
            m: u64,
        }
        #[derive(Clone, Copy, PartialEq)]
        pub struct Wrapped(pub u64);
        impl Montgomery {
            pub fn new(modulo: u64) -> Self {
                assert!(modulo % 2 != 0);
                assert!(modulo > 0);
                let r = R % modulo as u128;
                let r2 = r * r % modulo as u128;
                let m = {
                    let mut ret: u64 = 0;
                    let mut r = R;
                    let mut i = 1;
                    let mut t = 0;
                    while r > 1 {
                        if t % 2 == 0 {
                            t += modulo;
                            ret += i;
                        }
                        t >>= 1;
                        r >>= 1;
                        i <<= 1;
                    }
                    ret
                };
                Self { modulo, r2, m }
            }
            pub fn modulo(&self) -> u64 {
                self.modulo
            }
            fn reduce(&self, value: u128) -> u64 {
                let &Self { modulo, m, .. } = self;
                let mut ret =
                    (((((value & MASK) * m as u128) & MASK) * modulo as u128 + value) >> B) as u64;
                if ret >= modulo {
                    ret -= modulo;
                }
                ret
            }
            pub fn wrap(&self, a: u64) -> Wrapped {
                Wrapped(self.reduce(a as u128 * self.r2))
            }
            pub fn unwrap(&self, a: Wrapped) -> u64 {
                self.reduce(a.0 as u128)
            }
            pub fn mul(&self, a: Wrapped, b: Wrapped) -> Wrapped {
                Wrapped(self.reduce(a.0 as u128 * b.0 as u128))
            }
            pub fn add(&self, a: Wrapped, b: Wrapped) -> Wrapped {
                let mut t = a.0 as u128 + b.0 as u128;
                if t > self.modulo as u128 {
                    t -= self.modulo as u128;
                }
                Wrapped(t as u64)
            }
            pub fn sub(&self, a: Wrapped, b: Wrapped) -> Wrapped {
                let mut t = a.0 as u128;
                if t < b.0 as u128 {
                    t += self.modulo as u128;
                }
                t -= b.0 as u128;
                Wrapped(t as u64)
            }
            pub fn pow(&self, mut a: Wrapped, mut p: u64) -> Wrapped {
                let mut ret = self.wrap(1);
                while p > 0 {
                    if (p & 1) != 0 {
                        ret = self.mul(ret, a);
                    }
                    a = self.mul(a, a);
                    p >>= 1;
                }
                ret
            }
        }
    }
}