import qualified Control.Arrow             as Arrow
import           Data.Bits                 (Bits (unsafeShiftL, unsafeShiftR),
                                            FiniteBits (countTrailingZeros))
import           Data.Bool                 (bool)
import qualified Data.ByteString.Char8     as BSC8

import qualified Data.Vector.Unboxed       as VU
import qualified GHC.Integer.GMP.Internals as GMP

isPrime :: Int -> Bool
isPrime k
  | k <= 3 = k == 2 || k == 3
  | even k = False
  | otherwise = millerRabin k
  where
    millerRabin :: Int -> Bool
    millerRabin n
      | n < 2047                = loop [2]
      | n < 1373653             = loop [2,3]
      | n < 9080191             = loop [31,73]
      | n < 25326001            = loop [2,3,5]
      | n < 4759123141          = loop [2,7,61]
      | n < 1122004669633       = loop [2,13,23,1662803]
      | n < 2152302898747       = loop [2,3,5,7,11]
      | n < 3474749660383       = loop [2,3,5,7,11,13]
      | n < 341550071728321     = loop [2,3,5,7,11,13,17]
      | otherwise               = loop [2,325,9375,28178,450775,9780504,1795265022]
      where
        m = n - 1
        s = countTrailingZeros m
        d = m `unsafeShiftR` s

        loop [] = True
        loop (a:as)
          | powModInt (a `mod` n) d n /= 1 = (not allok) && loop as
          | otherwise = loop as
          where
            allok = all (\r -> (powModInt a ((1 `unsafeShiftL` r) * d) n) /= m) [0..(s - 1)]

powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo)
{-# INLINE powModInt #-}

type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parse1 :: IO Int
parse1 = readLn
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
-------------------------------------------------------------------------------
main :: IO ()
main = do
  n  <- parse1
  xs <- parseN n
  VU.mapM_ (BSC8.putStrLn . solve) xs

solve :: Int -> BSC8.ByteString
solve n = BSC8.pack $ bool (show n ++ " 0") (show n ++ " 1") (isPrime n)
-------------------------------------------------------------------------------