Spell Power Computation

In this problem, you are given an integer n and n spell strings. For each spell, you are required to compute its spell power. The spell power is defined as the length of the longest substring (contiguous sequence of characters) that appears at least twice in the spell. If no such substring exists, the spell power is 0.

More formally, for a given string \( s \) of length \( L \), you need to find the maximum integer \( l \) (where \( 1 \le l \le L-1 \)) such that there exists a substring \( x \) of length \( l \) which appears in \( s \) at least twice. In mathematical notation, the power \( P(s) \) of the spell can be expressed as:

[ P(s)=\max{l\mid \exists; x; \text{of length}; l ;\text{that occurs at least twice in}; s}]

If no repeated substring exists then \( P(s)=0 \).

Input/Output via Standard I/O

inputFormat

The first line contains an integer n, the number of spells. Each of the following n lines contains a non-empty string representing a spell.

outputFormat

Output a single line containing n integers separated by spaces. The \( i \)-th integer represents the spell power of the \( i \)-th spell.

## sample

3
ababab
abcdefg
aaaaa

4 0 4

</p>