#[allow(unused_imports)] use std::io::{stdout, BufWriter, Write}; fn main() { let out = stdout(); let mut out = BufWriter::new(out.lock()); inputv! { t:usize } for _ in 0..t { inputv! { n:u64 } writeln!(out, "{} {}", n, miller_rabin(n) as usize).unwrap(); } } //https://github.com/manta1130/competitive-template-rs use input::*; use primenumber::*; pub mod input { use std::cell::RefCell; use std::io; pub const SPLIT_DELIMITER: char = ' '; pub use std::io::prelude::*; thread_local! { pub static INPUT_BUFFER:RefCell>=RefCell::new(std::collections::VecDeque::new()); } #[macro_export] macro_rules! input_internal { ($x:ident : $t:ty) => { INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { let temp_str = input_line_str(); let mut split_result_iter = temp_str .split(SPLIT_DELIMITER) .map(|q| q.to_string()) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); let mut buf_split_result = String::new(); INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap()); let $x: $t = buf_split_result.parse().unwrap(); }; (mut $x:ident : $t:ty) => { INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { let temp_str = input_line_str(); let mut split_result_iter = temp_str .split(SPLIT_DELIMITER) .map(|q| q.to_string()) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); let mut buf_split_result = String::new(); INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap()); let mut $x: $t = buf_split_result.parse().unwrap(); }; } pub fn input_buffer_is_empty() -> bool { let mut empty = false; INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { empty = true; } }); empty } #[macro_export] macro_rules! inputv { ($i:ident : $t:ty) => { input_internal!{$i : $t} }; (mut $i:ident : $t:ty) => { input_internal!{mut $i : $t} }; ($i:ident : $t:ty $(,)*) => { input_internal!{$i : $t} }; (mut $i:ident : $t:ty $(,)*) => { input_internal!{mut $i : $t} }; (mut $i:ident : $t:ty,$($q:tt)*) => { input_internal!{mut $i : $t} inputv!{$($q)*} }; ($i:ident : $t:ty,$($q:tt)*) => { input_internal!{$i : $t} inputv!{$($q)*} }; } pub fn input_all() { INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { let mut temp_str = String::new(); std::io::stdin().read_to_string(&mut temp_str).unwrap(); let mut split_result_iter = temp_str .split_whitespace() .map(|q| q.to_string()) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); } pub fn input_line_str() -> String { let mut s = String::new(); io::stdin().read_line(&mut s).unwrap(); s.trim().to_string() } #[allow(clippy::match_wild_err_arm)] pub fn input_vector() -> Vec where T: std::str::FromStr, { let mut v: Vec = Vec::new(); let s = input_line_str(); let split_result = s.split(SPLIT_DELIMITER); for z in split_result { let buf = match z.parse() { Ok(r) => r, Err(_) => panic!("Parse Error",), }; v.push(buf); } v } #[allow(clippy::match_wild_err_arm)] pub fn input_vector_row(n: usize) -> Vec where T: std::str::FromStr, { let mut v = Vec::with_capacity(n); for _ in 0..n { let buf = match input_line_str().parse() { Ok(r) => r, Err(_) => panic!("Parse Error",), }; v.push(buf); } v } pub trait ToCharVec { fn to_charvec(&self) -> Vec; } impl ToCharVec for String { fn to_charvec(&self) -> Vec { self.to_string().chars().collect::>() } } } pub mod primenumber { use std::iter::Iterator; type ValueType = u64; pub trait GetDivisor { fn get_divisor(&self) -> Divisor; } macro_rules! GetDivisor_macro{ ($($t:ty),*) => { $( impl GetDivisor for $t { fn get_divisor(&self) -> Divisor { Divisor::calc(*self as ValueType) } })* }; } GetDivisor_macro!(u32, u64, u128, usize, i32, i64, i128, isize); pub trait GetPrimeFactorization { fn prime_factorization(&self) -> PrimeFactorization; } macro_rules! PrimeFactorization_macro{ ($($t:ty),*) => { $( impl GetPrimeFactorization for $t { fn prime_factorization(&self) -> PrimeFactorization { PrimeFactorization::calc(*self as ValueType) } })* }; } PrimeFactorization_macro!(u32, u64, u128, usize, i32, i64, i128, isize); pub struct Divisor { n: ValueType, cur: ValueType, flag: bool, } impl Divisor { pub fn calc(n: ValueType) -> Divisor { Divisor { n, cur: 1, flag: false, } } } impl Iterator for Divisor { type Item = ValueType; fn next(&mut self) -> Option { if self.cur * self.cur > self.n { None } else if self.flag { if self.cur * self.cur == self.n { return None; } self.flag = false; self.cur += 1; Some(self.n / (self.cur - 1)) } else { while self.n % self.cur != 0 { self.cur += 1; if self.cur * self.cur > self.n { return None; } } self.flag = true; Some(self.cur) } } } pub struct PrimeFactorization<'a> { n: ValueType, cur: ValueType, p_list: Option<&'a [ValueType]>, idx: usize, } impl<'a> PrimeFactorization<'a> { pub fn calc(n: ValueType) -> PrimeFactorization<'a> { PrimeFactorization { n, cur: 1, p_list: None, idx: 0, } } pub fn calc_fast(n: ValueType, p_list: &'a [ValueType]) -> PrimeFactorization<'a> { PrimeFactorization { n, cur: 1, p_list: Some(p_list), idx: 0, } } } impl<'a> Iterator for PrimeFactorization<'a> { type Item = ValueType; fn next(&mut self) -> Option { loop { if self.cur == 0 || self.cur > self.n { return None; } if self.p_list.is_some() { if self.idx >= self.p_list.unwrap().len() { return None; } self.cur = self.p_list.unwrap()[self.idx]; self.idx += 1; } else { self.cur += 1; } if self.cur * self.cur > self.n { if self.n != 1 { self.cur = 0; return Some(self.n); } return None; } if self.n % self.cur == 0 { self.n /= self.cur; if self.p_list.is_some() { self.idx -= 1; } self.cur -= 1; return Some(self.cur + 1); } } } } pub fn get_primelist(u: ValueType) -> Vec { let mut v = vec![true; u as usize + 1]; let mut r = vec![]; for i in 2..=u as usize { if v[i] { r.push(i as ValueType); let mut j = i * i; while j <= u as usize { v[j] = false; j += i; } } } r } pub fn get_mobius(n: ValueType) -> Vec { let mut r = vec![0, 1]; let p = get_primelist(n); for i in 2..=n { let mut f = PrimeFactorization::calc_fast(i as u64, &p).collect::>(); let count = f.len(); f.dedup(); if f.len() != count { r.push(0); } else { r.push(if f.len() % 2 == 0 { 1 } else { -1 }); } } r } fn modpow(mut s: u128, mut n: u128, p: u128) -> u128 { if p == 0 { return 1; } let mut t = s; s = 1; while n > 0 { if n & 1 != 0 { s *= t; s %= p; } n >>= 1; t *= t; t %= p; } s } pub fn miller_rabin(n: u64) -> bool { if n == 2 { return true; } if n == 1 || n % 2 == 0 { return false; } let (mut s, mut t) = (0, n - 1); while t % 2 == 0 { s += 1; t >>= 1; } let arr = if n <= 4_759_123_141 { vec![2, 7, 61] } else if n <= 3_825_123_056_546_413_051 { vec![2, 3, 5, 7, 11, 13, 17, 19, 23] } else { vec![2, 325, 9375, 28178, 450775, 9780504, 1795265022] } .iter() .filter(|&&q| q < n) .cloned() .collect::>(); for a in arr { if modpow(a as u128, t as u128, n as u128) == 1 { continue; } let mut flag = false; for i in 0..s { if modpow(a as u128, 2_u128.pow(i) * t as u128, n as u128) as u64 == n - 1 { flag = true; break; } } if !flag { return false; } } true } }