23495번 - Longest Lyndon Prefix 다국어

문제

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$.

제한

힌트