require 'openssl';gets;STDIN.each{|x| x.strip!; puts "#{x} #{OpenSSL::BN.new(x).prime? ? 1 : 0}"}