A. ABABABABA
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

For any positive integer $$$k$$$, we call a string $$$s$$$ a $$$k$$$-ababa string if there exist two non-empty strings $$$a$$$ and $$$b$$$ such that:

$$$$$$ s = \underbrace{(a + b) + (a + b) + \ldots + (a + b)}_{k} + a, $$$$$$

where $$$+$$$ denotes string concatenation. For example, the string aabaabaa is a $$$2$$$-ababa string, since we can choose $$$a =$$$ aa and $$$b =$$$ b. Strings $$$a$$$ and $$$b$$$ can be the same.

You are given a string $$$s$$$ of length $$$N$$$. For every integer $$$k$$$ from $$$1$$$ to $$$N$$$, output the length of the longest substring of $$$s$$$ that is a $$$k$$$-ababa string.

Input

The first line contains an integer $$$T$$$ — the number of test cases.

The first line of each test case contains an integer $$$N$$$ — the length of the string $$$s$$$.

The second line contains a string $$$s$$$ of length $$$N$$$, consisting of lowercase letters.

  • $$$1 \leq T \leq 10^5$$$
  • $$$1 \leq N \leq 3 \cdot 10^5$$$
  • It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
Output

For each test case, output a single line with $$$N$$$ integers. The $$$k$$$-th integer is the length of the longest $$$k$$$-ababa string that is a substring of $$$s$$$, or $$$0$$$ if none exists.

Example
Input
4
9
abcabcabc
11
mississippi
12
qwqwqwqwqwqq
18
ntuicpcpreliminary
Output
9 8 0 0 0 0 0 0 0
10 7 0 0 0 0 0 0 0 0 0
12 11 7 9 11 0 0 0 0 0 0 0
15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Note

In the first test case of the sample input, abcabcabc is a $$$1$$$-ababa string and bcabcabc is a $$$2$$$-ababa string.

In the second test case of the sample input, ississippi is a $$$1$$$-ababa string and ississi is a $$$2$$$-ababa string.