{-# LANGUAGE BangPatterns      #-}
{-# LANGUAGE OverloadedStrings #-}
import qualified Control.Arrow                     as Arrow
import           Data.Bits                         (Bits (unsafeShiftL, unsafeShiftR),
                                                    FiniteBits (countTrailingZeros))
import           Data.Bool                         (bool)
import qualified Data.ByteString.Builder           as BSB
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.List                         as List
import qualified Data.Vector.Fusion.Stream.Monadic as MS
import qualified Data.Vector.Unboxed               as VU
import qualified GHC.Integer.GMP.Internals         as GMP
import qualified System.IO                         as SysIO
-------------------------------------------------------------------------------
main :: IO ()
main = do
  n  <- readLn :: IO Int
  rep n $ \_ -> do
    p <- readLn :: IO Int
    BSB.hPutBuilder SysIO.stdout $ solve p

solve :: Int -> BSB.Builder
solve n = BSB.string8 $! show n <> (bool " 0\n"  " 1\n" (isPrime n))
-------------------------------------------------------------------------------
isPrime :: Int -> Bool
isPrime n
  | n <= 3    = n == 2 || n == 3
  | even n    = False
  | otherwise = mr n
  where
    mr k
      | k < 2047                = loop [2]
      | k < 1373653             = loop [2,3]
      | k < 9080191             = loop [31,73]
      | k < 25326001            = loop [2,3,5]
      | k < 4759123141          = loop [2,7,61]
      | k < 1122004669633       = loop [2,13,23,1662803]
      | k < 2152302898747       = loop [2,3,5,7,11]
      | k < 3474749660383       = loop [2,3,5,7,11,13]
      | k < 341550071728321     = loop [2,3,5,7,11,13,17]
      | otherwise               = loop [2,325,9375,28178,450775,9780504,1795265022]
      where
        !m = k - 1
        !s = countTrailingZeros m
        !d = m .>>. s
        check3 :: Int -> Bool
        check3 a = powModInt a d k /= 1
        {-# INLINE check3 #-}
        check4 :: Int -> Int -> Bool
        check4 a i = (powModInt a (d * (1 .<<. i)) k) /= m
        {-# INLINE check4 #-}
        loop [] = True
        loop (a:as)
          | check3 a && allok = False
          | otherwise = loop as
          where
            allok = all (check4 a) [0..(s - 1)]
-------------------------------------------------------------------------------
rep :: Monad m => Int -> (Int -> m ()) -> m ()
rep n = flip MS.mapM_ (stream 0 n)
{-# INLINE rep #-}

stream :: Monad m => Int -> Int -> MS.Stream m Int
stream !l !r = MS.Stream step l
  where
    step x
        | x < r = return $ MS.Yield x (x + 1)
        | otherwise = return MS.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] stream #-}

infixl 8 .>>., .<<.
(.>>.) :: Bits i => i -> Int -> i
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}

(.<<.) :: Bits i => i -> Int -> i
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}

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

parse1 :: IO Int
parse1 = readLn
{-# INLINE parse1 #-}

parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
{-# INLINE parseN #-}