시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB29131254.545%

문제

A word $w$ is a lyndon word if and only if it is strictly smaller than all its proper suffixes. For example, aab is a lyndon word, while aa is not a lyndon word.

Chiaki has a string $s_1s_2\dots s_n$ of length $n$. She would like to know $l_i$, that is the length of the longest prefix of $s_i s_{i + 1} \dots s_{n}$ which is a lyndon word.

입력

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \leq n \leq 10^5$). The second line contains a string $s_1 s_2 \dots s_n$ consists of lowercase characters.

The sum of all $n$ does not exceed $10^5$.

출력

For each test case, output $n$ integers denoting $l_1, l_2, \dots, l_n$.

예제 입력 1

3
3
aaa
3
aab
3
cba

예제 출력 1

1 1 1
3 2 1
1 1 1