(in-package :cl-user)
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter *opt*
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload '(:cl-debug-print :fiveam :cp/util) :silent t)
  #+swank (use-package :cp/util :cl-user)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t))))
  #+sbcl (setq *random-state* (seed-random-state (nth-value 1 (get-time-of-day)))))
#+swank (set-dispatch-macro-character #\# #\> #'cl-debug-print:debug-print-reader)

(macrolet ((def (b)
             `(progn (deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))
                     (deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))))
           (define-int-types (&rest bits) `(progn ,@(mapcar (lambda (b) `(def ,b)) bits))))
  (define-int-types 2 4 7 8 15 16 31 32 62 63 64))

(defconstant +mod+ 1000000007)

(defmacro dbg (&rest forms)
  #+swank (if (= (length forms) 1)
              `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
              `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format*
          (if (typep obj 'double-float) 'double-float *read-default-float-format*)))
    (prog1 (princ obj stream) (terpri stream))))

;; BEGIN_INSERTED_CONTENTS
(defpackage :cp/tzcount
  (:use :cl)
  (:export #:tzcount))
(in-package :cp/tzcount)

(declaim (inline tzcount))
(defun tzcount (x)
  "Returns the number of trailing zero bits. Note that (TZCOUNT 0) = -1."
  (- (integer-length (logand x (- x))) 1))

;;;
;;; Primality test (deterministic Miller-Rabin)
;;;

;; Tuned for SBCL on x86-64 ((INTEGER 0 #.MOST-POSITIVE-FIXNUM) ==
;; (UNSIGNED-BYTE 62))

(defpackage :cp/primality
  (:use :cl :cp/tzcount)
  (:export #:prime-p))
(in-package :cp/primality)

(defun %strong-probable-prime-p (n base)
  (declare (optimize (speed 3))
           ((unsigned-byte 63) n base))
  (or (= n base)
      (labels ((mod-power (base power)
                 (declare ((unsigned-byte 63) base power))
                 (loop with res of-type (unsigned-byte 63) = 1
                       while (> power 0)
                       when (oddp power)
                       do (setq res (mod (* res base) n))
                       do (setq base (mod (* base base) n)
                                power (ash power -1))
                       finally (return res))))
        (let* ((d (floor (- n 1) (logand (- n 1) (- 1 n))))
               (y (mod-power base d)))
          (declare ((unsigned-byte 63) y))
          (or (= y 1)
              (= y (- n 1))
              (let ((s (tzcount (- n 1))))
                (loop repeat (- s 1)
                      do (setq y (mod (* y y) n))
                         (when (<= y 1) (return nil))
                         (when (= y (- n 1)) (return t)))))))))

;; https://primes.utm.edu/prove/prove2_3.html
;; TODO: more efficient SPRP
(defun prime-p (n)
  (declare ((unsigned-byte 63) n))
  (cond ((<= n 1) nil)
        ((evenp n) (= n 2))
        ((< n 4759123141)
         (loop for base in '(2 7 61)
               always (%strong-probable-prime-p n base)))
        ((< n 2152302898747)
         (loop for base in '(2 3 5 7 11)
               always (%strong-probable-prime-p n base)))
        ;; NOTE: branches below are not tested
        (t
         (loop for base in '(2 325 9375 28178 450775 9780504 1795265022)
               always (%strong-probable-prime-p n base)))))

;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/primality :cl-user))
(in-package :cl-user)

;;;
;;; Body
;;;

(defun main ()
  (let* ((n (read)))
    (write-string
     (with-output-to-string (*standard-output* nil :element-type 'base-char)
       (dotimes (_ n)
         (let ((x (read-fixnum)))
           (format t "~D ~D~%"
                   x
                   (if (prime-p x)
                       1
                       0))))))))

#-swank (main)

;;;
;;; Test
;;;

#+swank
(progn
  (defparameter *lisp-file-pathname* (uiop:current-lisp-file-pathname))
  (setq *default-pathname-defaults* (uiop:pathname-directory-pathname *lisp-file-pathname*))
  (uiop:chdir *default-pathname-defaults*)
  (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *lisp-file-pathname*))
  (defparameter *problem-url* "https://yukicoder.me/problems/no/3030"))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

#+(and sbcl (not swank))
(eval-when (:compile-toplevel)
  (when (or (> sb-c::*compiler-warning-count* 0)
            sb-c::*undefined-warnings*)
    (error "count: ~D, undefined warnings: ~A"
           sb-c::*compiler-warning-count*
           sb-c::*undefined-warnings*)))

;; To run: (5am:run! :sample)
#+swank
(5am:test :sample
  (5am:is
   (equal "10 0
2 1
1 0
5 1
"
          (run "4
10
2
1
5
" nil))))