pub use npk_cp_lib::prelude::*;

use std::{io::stdin, num::NonZeroU64};

use input::{bind, FastInput};
use proconio::fastout;

#[fastout]
fn main() {
    let mut input: FastInput<std::io::StdinLock<'_>> = FastInput::new(stdin().lock());
    bind! { input >> n: usize, x: [u64; n], }

    for x in x {
        if primality_test(x) {
            println!("{x} 1")
        } else {
            println!("{x} 0")
        }
    }
}

struct Divisor64 {
    d: u64,
    /// `(1 << 128).div_ceil(d)`
    r: u128,
}

impl Divisor64 {
    const fn new(d: NonZeroU64) -> Self {
        let d = d.get();
        let r = !0 / d as u128 + 1;

        Self { d, r }
    }

    #[inline(always)]
    const fn modulo(&self, x: u128) -> u64 {
        let (hi, lo) = {
            let x = self.r.wrapping_mul(x as u128).wrapping_mul(self.d as u128);
            (x >> 64, x & (!0 >> 64))
        };
        (hi.wrapping_mul(self.d as u128)
            .wrapping_add((lo * self.d as u128) >> 64)
            >> 64) as u64
    }

    #[inline(always)]
    const fn pow(&self, mut x: u64, mut exp: u64) -> u64 {
        let mut res = 1;

        while exp > 0 {
            if exp & 1 == 1 {
                res = self.modulo(res as u128 * x as u128);
            }

            exp >>= 1;
            x = self.modulo(x as u128 * x as u128)
        }

        res
    }
}

// from <https://miller-rabin.appspot.com/>
/// x < 350_269_456_337
static SET3: [u64; 3] = [
    4230279247111683200,
    14694767155120705706,
    16641139526367750375,
];
/// x < 2^64
static SET7: [u64; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];

/// Performs deterministic Miller-Rabin primality test.
///
/// # Time complexity
///
/// *O*(log *x*)
pub const fn primality_test(x: u64) -> bool {
    /// `x` is prime iff `(test >> x) & 1 == 1`
    const SMALL_PRIME: u64 = {
        let mut test = 0;
        let mut x = 64;
        while x > 0 {
            x -= 1;

            test = (test << 1) | if primality_test_naive(x) { 1 } else { 0 };
        }
        test
    };

    /// remove multiples of 2, 3 or 5
    const MAY_BE_PRIME_30: u32 = {
        let mut table = 0;

        let mut n = 0;
        while n < 30 {
            table |= if n % 2 == 0 || n % 3 == 0 || n % 5 == 0 {
                0 // composite
            } else {
                1 // may be prime
            } << n;
            n += 1;
        }

        table
    };

    if x < 64 {
        return (SMALL_PRIME >> x) & 1 == 1;
    } else if (MAY_BE_PRIME_30 >> x % 30) & 1 == 0 || x % 7 == 0 {
        return false;
    }

    let (s, d) = {
        let x = x - 1;
        let s = x.trailing_zeros();
        (s - 1, x >> s)
    };

    let divisor = Divisor64::new(NonZeroU64::new(x).unwrap());

    let witness = if x < 350_269_456_337 {
        SET3.as_slice()
    } else {
        SET7.as_slice()
    };

    let mut i = 0;
    'test: while i < witness.len() {
        let mut w = divisor.modulo(witness[i] as u128);
        i += 1;

        if w == 0 {
            continue;
        }

        w = divisor.pow(w, d);
        if w == 1 || w == x - 1 {
            continue;
        }

        let mut s = s;
        while s > 0 {
            s -= 1;

            w = divisor.modulo(w as u128 * w as u128);
            if w == x - 1 {
                continue 'test;
            }
        }

        return false;
    }

    true
}

const fn primality_test_naive(x: u64) -> bool {
    if x < 2 {
        return false;
    }

    let mut d = 1;
    while d < x.isqrt() {
        d += 1;

        if x % d == 0 {
            return false;
        }
    }

    true
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 

#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod npk_cp_lib {
    pub(crate) mod crates {
        pub mod from_bytes {use std::num::IntErrorKind;#[inline]const fn parse_8_digits(bytes:[u8;8])->Result<u64,IntErrorKind>{let mut n=u64::from_le_bytes(bytes)^0x3030_3030_3030_3030;if(n&0xf0f0_f0f0_f0f0_f0f0)|(n.wrapping_mul(7)&0x4040_4040_4040_4040)==0{n=(n.wrapping_mul((10<<8)+1)>>8)&0x00ff_00ff_00ff_00ff;n=(n.wrapping_mul((100<<16)+1)>>16)&0x0000_ffff_0000_ffff;n=n.wrapping_mul((10000<<32)+1)>>32;Ok(n)}else{Err(IntErrorKind::InvalidDigit)}}#[inline]const fn parse_4_digits(bytes:[u8;4])->Result<u32,IntErrorKind>{let mut n=u32::from_le_bytes(bytes)^0x3030_3030;if(n&0xf0f0_f0f0)|(n.wrapping_mul(7)&0x4040_4040)==0{n=(n.wrapping_mul((10<<8)+1)>>8)&0x00ff_00ff;n=n.wrapping_mul((100<<16)+1)>>16;Ok(n)}else{Err(IntErrorKind::InvalidDigit)}}pub trait FromBytes:Sized{type Err;fn from_bytes(bytes:&[u8])->Result<Self,Self::Err>;}macro_rules!parse_digits{($t:ty,$digits:expr,$mul:tt,$add:ident$(,$overflow:path)*)=>{{let(remainder,chunks)=$digits.as_rchunks::<8>();let mut n=0 as$t;if remainder.len()>4{let mut digits=[b'0';8];digits[8-remainder.len()..].copy_from_slice(remainder);n=n.$add(parse_8_digits(digits)?as$t)$(.ok_or($overflow)?)*;}else{let mut digits=[b'0';4];digits[4-remainder.len()..].copy_from_slice(remainder);n=n.$add(parse_4_digits(digits)?as$t)$(.ok_or($overflow)?)*;}for chunk in chunks{n=n.$mul(1_0000_0000)$(.ok_or($overflow)?)*;n=n.$add(parse_8_digits(*chunk)?as$t)$(.ok_or($overflow)?)*;}n}};}macro_rules!from_bytes_impl{($($t:ty)*)=>{$(impl FromBytes for$t{type Err=IntErrorKind;fn from_bytes(bytes:&[u8])->Result<Self,Self::Err>{if bytes.is_empty(){return Err(IntErrorKind::Empty);}#[allow(unused_comparisons)]let is_signed_ty=<$t>::MIN<0;let(is_positive,digits)=match bytes{[b'+'|b'-']=>return Err(IntErrorKind::InvalidDigit),[b'+',rest@..]=>(true,rest),[b'-',rest@..]if is_signed_ty=>(false,rest),_=>(true,bytes),};let never_overflow={const MAX_DIGITS_LEN:usize=<$t>::MAX.ilog10()as usize+1;const LEADING_BYTE_OF_MAX:u8=(<$t>::MAX/(10 as$t).pow(MAX_DIGITS_LEN as u32-1))as u8+b'0';(digits.len()<MAX_DIGITS_LEN)||(digits.len()==MAX_DIGITS_LEN&&digits[0]<LEADING_BYTE_OF_MAX)};let n=if never_overflow{if is_positive{parse_digits!($t,digits,wrapping_mul,wrapping_add)}else{parse_digits!($t,digits,wrapping_mul,wrapping_sub)}}else{if is_positive{parse_digits!($t,digits,checked_mul,checked_add,IntErrorKind::PosOverflow)}else{parse_digits!($t,digits,checked_mul,checked_sub,IntErrorKind::NegOverflow)}};Ok(n)}})*};}from_bytes_impl!(i32 u32 i64 u64 i128 u128 isize usize);macro_rules!from_bytes_impl_small_unsigned{($($t:ty)*)=>{$(impl FromBytes for$t{type Err=IntErrorKind;fn from_bytes(bytes:&[u8])->Result<Self,Self::Err>{let v=u32::from_bytes(bytes)?;if v><$t>::MAX as u32{Err(IntErrorKind::PosOverflow)}else{Ok(v as$t)}}})*};}from_bytes_impl_small_unsigned!(u8 u16);macro_rules!from_bytes_impl_small_signed{($($t:ty)*)=>{$(impl FromBytes for$t{type Err=IntErrorKind;fn from_bytes(bytes:&[u8])->Result<Self,Self::Err>{let v=i32::from_bytes(bytes)?;if v< <$t>::MIN as i32{Err(IntErrorKind::NegOverflow)}else if v><$t>::MAX as i32{Err(IntErrorKind::PosOverflow)}else{Ok(v as$t)}}})*};}from_bytes_impl_small_signed!(i8 i16);}
        pub mod input {use crate::npk_cp_lib::preludes::input::*;pub use crate::npk_cp_lib::macros::input::*;use std::io::{self,BufRead,ErrorKind};use from_bytes::FromBytes;pub struct FastInput<R>where R:BufRead,{reader:R,buf:Vec<u8>,}impl<R>FastInput<R>where R:BufRead,{#[inline]pub fn new(reader:R)->Self{Self{reader,buf:Vec::new(),}}pub fn next_token<T>(&mut self)->Option<T>where T:FromBytes,{{let buf=self.reader.fill_buf().ok()?;let i=buf.iter().take_while(|b|b.is_ascii_whitespace()).count();self.reader.consume(i);}let buf=self.reader.fill_buf().ok()?;if let Some(n)=buf.iter().position(|b|b.is_ascii_whitespace()){let token=T::from_bytes(&buf[..n]);self.reader.consume(n+1);token}else{let mut buf=std::mem::take(&mut self.buf);self.next_bytes(&mut buf).ok()?;let token=T::from_bytes(&buf);buf.clear();self.buf=buf;token}.ok()}pub fn next_token_vec<T>(&mut self,len:usize)->Option<Vec<T>>where T:FromBytes,{let mut vec=Vec::with_capacity(len);for _ in 0..len{vec.push(self.next_token()?)}Some(vec)}pub fn next_bytes(&mut self,buf:&mut Vec<u8>)->io::Result<()>{{let buf=self.reader.fill_buf()?;let i=buf.iter().take_while(|b|b.is_ascii_whitespace()).count();self.reader.consume(i);}loop{let available=match self.reader.fill_buf(){Ok(buf)=>buf,Err(e)if e.kind()==ErrorKind::Interrupted=>continue,Err(e)=>return Err(e),};let(done,used)=if let Some(n)=available.iter().position(|b|b.is_ascii_whitespace()){buf.extend_from_slice(&available[..n]);(true,n+1)}else{buf.extend_from_slice(&available);(false,available.len())};self.reader.consume(used);if done||(used==0){return Ok(());}}}}#[macro_export]macro_rules!npk_cp_lib_macro_def_input_parse{(@source[$source:ident]@rest$(,)?)=>{};(@source[$source:ident]@rest[$($item:tt)+]$(,)?)=>{$crate::npk_cp_lib::crates::input::parse!(@vec@source[$source]@item[$($item)+]@rest)};(@source[$source:ident]@rest($($item:tt)+)$(,)?)=>{$crate::npk_cp_lib::crates::input::parse!(@tuple@source[$source]@item[$($item)+]@rest)};(@source[$source:ident]@rest Bytes$(with capacity$len:expr)?$(,)?)=>{{let mut bytes=Vec::with_capacity(0$(+TryInto::<usize>::try_into($len).unwrap())?);$source.next_bytes(&mut bytes).unwrap();bytes}};(@source[$source:ident]@rest String$(with capacity$len:expr)?$(,)?)=>{{String::from_utf8($crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest Bytes$(with capacity$len)?)).unwrap()}};(@source[$source:ident]@rest$item:ty$(,)?)=>{$source.next_token::<$item>().unwrap()};(@vec@source[$source:ident]@item[[$($item:tt)+];$len:expr]@rest)=>{(0..$len).into_iter().map(|_|$crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest[$($item)+])).collect::<Vec<_>>()};(@vec@source[$source:ident]@item[($($item:tt)+);$len:expr]@rest)=>{(0..$len).into_iter().map(|_|$crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest($($item)+))).collect::<Vec<_>>()};(@vec@source[$source:ident]@item[$item:tt;$len:expr]@rest)=>{(0..$len).into_iter().map(|_|$crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest$item)).collect::<Vec<_>>()};(@tuple@source[$source:ident]@item[$($item:tt),+$(,)?]@rest)=>{($($crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest$item),)+)};(@source[$source:ident]$($rest:tt)*)=>{std::compile_error!("failed to parse")};($source:ident>>$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest$($rest)*)};}macro_rules!parse{($($tt:tt)*)=>(crate::npk_cp_lib_macro_def_input_parse!{$($tt)*})}#[macro_export]macro_rules!npk_cp_lib_macro_def_input_bind{(@source[$source:ident]@rest)=>{};(@source[$source:ident]@rest,$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*)};(@source[$source:ident]@rest mut$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@mut[mut]@rest$($rest)*)};(@source[$source:ident]@rest$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@mut[]@rest$($rest)*)};(@source[$source:ident]@mut[$($mut:tt)?]@rest$ident:tt:$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@mut[$($mut)?]@ident[$ident]@rest$($rest)*)};(@source[$source:ident]@mut[$($mut:tt)?]@ident[$ident:tt]@rest($($t:tt)+)$($rest:tt)*)=>{let$($mut)?$ident=$crate::npk_cp_lib::crates::input::parse!($source>>($($t)+));$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*)};(@source[$source:ident]@mut[$($mut:tt)?]@ident[$ident:tt]@rest[$($t:tt)+]$($rest:tt)*)=>{let$($mut)?$ident=$crate::npk_cp_lib::crates::input::parse!($source>>[$($t)+]);$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*)};(@source[$source:ident]@mut[$($mut:tt)?]@ident[$ident:tt]@rest$t:tt,$($rest:tt)*)=>{let$($mut)?$ident=$crate::npk_cp_lib::crates::input::parse!($source>>$t);$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*);};(@source[$source:ident]@mut[$($mut:tt)?]@ident[$ident:tt]@rest$t:tt)=>{let$($mut)?$ident=$crate::npk_cp_lib::crates::input::parse!($source>>$t);$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest);};(@source[$source:ident]$($rest:tt)*)=>{std::compile_error!("failed to parse")};($source:ident>>$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*)};}macro_rules!bind{($($tt:tt)*)=>(crate::npk_cp_lib_macro_def_input_bind!{$($tt)*})}}
    }

    pub(crate) mod macros {
        pub mod from_bytes {}
        pub mod input {pub use crate::{npk_cp_lib_macro_def_input_bind as bind,npk_cp_lib_macro_def_input_parse as parse};}
    }

    pub(crate) mod prelude {pub use crate::npk_cp_lib::crates::*;}

    mod preludes {
        pub mod from_bytes {}
        pub mod input {pub(in crate::npk_cp_lib)use crate::npk_cp_lib::crates::from_bytes;}
    }
}