H. Distinct Substrings
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Let $$$\Sigma$$$ be an alphabet, which in this problem is the set of lowercase English letters. Let $$$\Sigma^+$$$ denote the set of all non-empty strings over $$$\Sigma$$$. For a string $$$t$$$, let $$$|t|$$$ denote its length, and let $$$t[i..j]$$$ denote the substring of $$$t$$$ starting at position $$$i$$$ and ending at position $$$j$$$.

You are given a string $$$s \in \Sigma^+$$$. For a string $$$p$$$, define $$$\operatorname{occ}_s(p)=\{i \mid s[i..i+|p|-1]=p\}$$$.

For all $$$1 \le i \le |s|$$$, compute:

$$$$$$f_s(i)=\lvert\left\{w \in \Sigma^+ \mid \exists x \in \operatorname{occ}_s(w), x \le i \le x + |w|-1\right\}\rvert$$$$$$

In other words, $$$f_s(i)$$$ is the number of distinct substrings of $$$s$$$ that cover position $$$i$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The only line of each test case contains the string $$$s$$$ ($$$1 \le |s| \le 10^6$$$).

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output $$$|s|$$$ integers, where the $$$i$$$-th integer represents $$$f_s(i)$$$.

Example
Input
4
a
aaaaa
abaaa
abcbcba
Output
1 
5 5 5 5 5 
5 8 9 7 5 
7 12 15 15 15 12 7