C. Play With Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters.

For each index $$$i$$$, calculate what is the maximum length of the palindromic substring which includes $$$i$$$-th index.

In other words, for each index $$$i$$$, find the maximum value of $$$r - l + 1$$$ where $$$s[l\ldots r]$$$ is a palindrome and $$$(1 \le l \le i \le r \le n)$$$

Suppose s = acab. Hence, for index $$$1$$$, $$$2$$$, and $$$3$$$ the answer is $$$3$$$ (acab, the underlined part is the maximum such palindromic substring), for the index, $$$4$$$ the answer is $$$1$$$ (acab, the underlined part is the maximum such palindromic substring).

A string $$$s[1\ldots n]$$$ of length $$$n$$$ is palindromic if $$$s[i]=s[n-i+1]$$$ for every $$$1 \le i \le n$$$.

The string $$$s[l\ldots r]$$$ is a substring of string $$$s[1\ldots n]$$$ for every $$$1 \le l \le r \le n$$$.

Input

The input data contains several test cases. The first line contains one integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — length of the string $$$s$$$.

The second line for each test case contains a single string, $$$s$$$ of $$$n$$$ lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers — $$$i$$$-th of which is the answer for index $$$i$$$.

Example
Input
2
10
astthemota
9
adaadaaxz
Output
1 1 2 2 1 1 1 1 1 1 
6 6 6 6 6 6 5 1 1
Note

For the 1st test, for index: $$$3$$$ and $$$4$$$ we can select palindrome substring tt (astthemota). But for other indexes, we can't select any palindromic substring of more than $$$1$$$ length, which includes that index also.