require 'prime'

res = ''

gets
$<.read.split.map(&:to_i).each do |x|
  res << x.to_s << (x.prime? ? " 1\n" : " 0\n")
end

puts res