如果一个字符串 $w$ 严格小于它的所有真后缀，则称其为 Lyndon 词。例如，aab 是一个 Lyndon 词，而 aa 不是。
Chiaki 有一个长度为 $n$ 的字符串 $s_1s_2 \dots s_n$。她想知道 $l_i$，即 $s_i s_{i+1} \dots s_n$ 的最长 Lyndon 前缀的长度。
输入格式
输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。对于每组测试数据：
第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。第二行包含一个由小写字母组成的字符串 $s_1s_2 \dots s_n$。
所有 $n$ 的总和不超过 $10^5$。
输出格式
对于每组测试数据，输出 $n$ 个整数，表示 $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