{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE MagicHash #-}

import qualified Control.Arrow               as Arrow
import qualified Control.Monad               as Monad
import qualified Data.Bool                   as Bool
import qualified Data.Bits                   as Bits
import qualified Data.ByteString.Char8       as BSC8
import qualified Data.Foldable               as Foldable
import qualified Data.List                   as List
import qualified Data.Vector                 as V
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Word                   as Word
import           Unsafe.Coerce
-----------
-- input --
-----------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 =  (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 =  (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine

main :: IO ()
main = do
  n <- parse1
  xs <- parseN n
  Monad.forM_ [0..n-1] $ \i -> do
    putStrLn $ show (xs VU.! i) ++ " " ++ Bool.bool "0" "1" (millerRabin $ xs VU.! i) 

-- n < 4759123141 までのチェック
checkers1 :: [Int]
checkers1 = [2, 7, 61]
-- 4759123141 <= n < 341550071728321 の範囲をチェック
checkers2 :: [Int]
checkers2 = [2, 3, 5, 7, 11, 13, 17]
-- 341550071728321 <= n < 9223372036854775808 の範囲をチェック
checkers3 :: [Int]
checkers3 = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]

-- millerRabin :: Int -> Bool
millerRabin :: Int -> Bool
millerRabin n
  |  n <= 1 = False
  |  n == 2
  || n == 3
  || n == 5
  || n == 7 = True
  |  even n = False
  |  otherwise = mrCheck n

powMod :: Int -> Int -> Int -> Int
powMod x n modulus
  | x > modulus = powMod (x `mod` modulus) n modulus
  | n == 0 = 1
  | n == 1 = x `mod` modulus
  | x == 0 = 0
  | x == 1 = 1
  | even n    = z * z `mod` modulus
  | otherwise = z * z * (x `mod` modulus) `mod` modulus
  where z = powMod x (n `div` 2) modulus

div2beki :: Int -> Int
div2beki m
  | odd m = m
  | otherwise = div2beki (m `div` 2)
div2count :: Int -> Int
div2count m
  | odd m = 0
  | otherwise = 1 + div2count (m `div` 2)

-- p は 9 以上の奇数
mrCheck :: Int -> Bool
mrCheck p
  | p < 4759123141      = xBool   && yBool
  | p < 341550071728321 = xBool'  && yBool'
  | otherwise           = xBool'' && yBool''
  where
    m = p - 1
    d = div2beki m
    s = div2count m
    xs = [0..s-1]
    xBool   = all id $ map (\a -> powMod a d p /= 1) checkers1
    xBool'  = all id $ map (\a -> powMod a d p /= 1) checkers2
    xBool'' = all id $ map (\a -> powMod a d p /= 1) checkers3
    yBool   = null $ concat $ Monad.forM xs (\i -> filter id $ [powMod a ((2 ^ i) * d) p == (p - 1) | a <- checkers1])
    yBool'  = null $ concat $ Monad.forM xs (\i -> filter id $ [powMod a ((2 ^ i) * d) p == (p - 1) | a <- checkers2])
    yBool'' = null $ concat $ Monad.forM xs (\i -> filter id $ [powMod a ((2 ^ i) * d) p == (p - 1) | a <- checkers3])