(defconstant +mod+ 1000000009)

(defun main (&rest argv)
  (declare (ignorable argv))
  (let* ((query (read))
         (dp (make-array 100001 :initial-element 1)))
    (loop for i from 1 to 9 do
          (loop for j from i to 100000 do
                (setf (aref dp j) (+ (aref dp j) (aref dp (- j i)))
                      (aref dp j) (mod (aref dp j) +mod+))))
    (dotimes (_ query)
      (format t "~d~%" (aref dp (floor (read) 111111))))))

(main)