require 'prime'

res = ''
gets.to_i.times do
  x = gets.to_i
  res << x.to_s << (x.prime? ? " 1\n" : " 0\n")
end

puts res