require 'prime'

T = gets.to_i

T.times do
  a, pv = gets.split.map(&:to_i)

  if pv.prime?
    res = 1
    b = a % pv
    v = 1

    pv.times do
      v *= a
      v %= pv

      res *= v
      res %= pv
    end

    puts res
  else
    puts -1
  end
end