題目描述

在一個全由小階英文字母所組成的字符串中，有些子字符串是重複出現多於一次。現在我們想找出在這些重複出現的子字符串中最長的一個字符串的長度是多少？重複的字符串可以部份自我重叠。

詳見下面說明。

現在我們有 K 個這樣的字串，對每個字符串我們都要找出它的最長重複子字符串的長度。

輸入格式

輸入的第一行上有一個正整 K，它代表共有多少個字符串我們需要處理。（1≤K≤5 )

隨後的 K 行中，每行有一個上面所述的字符串。字符串最長的長度為 4,000 個字符。

輸出資料應叭含有 K 個整數，它們順序表示在對應的輸入字符串中，最長的重複子字符串的長度。每個輸出數字應單獨放在一行上，即輸出應該共有 K 。

3
abcxyzabcxghilqn
wxyzmnklogi
abababababaabc

4
0
9

上例的第三個輸入中，重複的子字符串為 ababababa ( abababababaabc 及 abababababaabc )