對稱的事物往往令人感到美麗。

回文就是一個對稱的例子。當一個字串反過來寫依然不變的時候我們就說它是一個回文。例如「上海自來水來自海上」和 "noon" 都是回文；而 "XDD" 則不是回文。在一個字串中找出最長的回文子字串也是資訊競賽中的經典題型，藉由精巧的 Manacher's algorithm 可以在線性時間內解決這個問題。

但太多對稱的東西也讓人感到審美疲勞，競賽中只考察經典題也有點無聊。字串界之王蚯蚯決定要另闢蹊徑，探索非對稱之美。因此他想要考考你，如何在字串 s 中，找出最長的「非回文」子字串呢？

蚯蚯很好心的提醒你有關子字串的定義。如果一個字串 t 與 s 中的一個連續區段相等的話，我們就說 t 是 s 的一個子字串。例如 s = "meow" 時，"meow" 跟 "eo" 都是 s 的子字串；而 "mw" 則不是。 

輸入的第一行有一個整數 T，代表共有幾筆測試資料。 

每筆測試資料恰有一行，包含一個字串 s。

• 字串 s 的長度至少為 1 且不超過 10⁶
• 字串 s 僅由小寫英文字母構成 

3
meow
aaaa
noon

4
0
3