(define (z-algorithm s)
  (let*
    ((n (string-length s)) (z (make-vector n 0)) (l 0) (r 0))
    (vector-set! z 0 n)
    (do
      ((i 1 (+ i 1)))
      ((= i n) z)
      (when (<= i r)
        (if (< (- (+ r 1) i) (vector-ref z (- i l)))
          (vector-set! z i (- (+ r 1) i))
          (vector-set! z i (vector-ref z (- i l)))))
      (while (and (< (+ i (vector-ref z i)) n) (equal? (string-ref s (vector-ref z i)) (string-ref s (+ i (vector-ref z i)))))
        (vector-set! z i (+ 1 (vector-ref z i))))
      (when (< r (+ (- i 1) (vector-ref z i)))
        (set! l i)
        (set! r (+ (- i 1) (vector-ref z i)))))))


(define yuki2454
  (let*
    ((t (read)) (_ (read-line)))
    (dotimes (t)
      (let*
        ((n (read)) (_ (read-line)) (s (read-line)) (z (z-algorithm s)) (a 0))
        (do
          ((i 1 (+ i 1)))
          ((= i n))
          (let ((y (vector-ref z i)))
            (cond
              ((< i y)
                (set! a (+ a 1)))
              ((and (< (+ i y) n) (or (equal? i y) (char<? (string-ref s y) (string-ref s (+ i y)))))
                (set! a (+ a 1)))
              (else))))
        (print a)))))