가장 긴 Lyndon 접두사

단어 $w$가 자신의 모든 진접미사보다 사전순으로 엄격히 작으면, $w$를 Lyndon 단어라고 한다. 예를 들어 aab는 Lyndon 단어이고, aa는 Lyndon 단어가 아니다.

치아키에게 길이 $n$의 문자열 $s_1s_2\dots s_n$이 있다. 치아키는 각 $i$에 대해 $s_i s_{i+1} \dots s_n$의 접두사 중 Lyndon 단어인 가장 긴 접두사의 길이 $l_i$를 알고 싶어 한다.

여러 개의 테스트 케이스가 주어진다. 첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10^5$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫째 줄에 정수 $n$ ($1 \leq n \leq 10^5$)이 주어진다. 둘째 줄에 소문자로만 이루어진 길이 $n$의 문자열 $s_1 s_2 \dots s_n$이 주어진다.

모든 $n$의 합은 $10^5$을 넘지 않는다.

각 테스트 케이스마다 $n$개의 정수 $l_1, l_2, \dots, l_n$을 출력한다.