use std::io::Read; fn read() -> T { let token: String = std::io::stdin() .bytes() .map(|c| c.ok().unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect(); token.parse().ok().unwrap() } fn mpow(a: i64, x: i64, mo: i64) -> i64 { if x == 0 { 1 } else if x == 1 { a } else if (x & 1) == 1 { a * mpow(a, x - 1, mo) } else { mpow(a * a, x / 2, mo) } } fn main() { let n = 5 * 100000 + 1; let mut is_prime = vec![true; n]; is_prime[1] = false; for i in 2..n { if i * i >= n { break; } if is_prime[i] { let mut j = i * 2; while j < n { is_prime[j] = false; j += i; } } } let t: usize = read(); for _ in 0..t { let a: i64 = read(); let p: i64 = read(); let ans = if is_prime[p as usize] { mpow(a, p * p / 2 % (p - 1), p) } else { -1 }; println!("{}", ans); } }