require 'openssl'
require 'prime'

T = gets.to_i
memo = Hash.new

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

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

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