require 'openssl'

T = gets.to_i
memo = Hash.new

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

  if memo[pv].nil?
    memo[pv] = bn.prime?
  end

  if memo[pv]
    if a.gcd(pv) == 1
      puts 1
    else
      puts 0
    end
  else
    puts -1
  end
end