TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Description

彥人有一個神奇的嗜好,就是最愛在外面和蝴蝶一起玩了!有一天,彥人追隨著一隻蝴蝶跑,沿著溪流前進,發現蝴蝶飛進山中的一個山洞中,彥人也隨著進去了,穿越山洞後,映入眼簾的是一個充滿蝴蝶的村莊,彥人便在村莊待了一段時間。

在這段時間中,彥人發現蝴蝶有一個神奇的性質:
1. 每隻蝴蝶都可以用字母所組成的字串表示,又因為蝴蝶翅膀左右對稱,所以該字串從正中間切,往左右看都一樣(若長度為奇數,則最中間的字元可以視為身體;若長度為偶數,則該蝴蝶可能沒有身體)。 舉例來說,meowoem 可以拆成 meowwoem,從最中間往外看都是 woem;而 yeey 則可拆成 yeey
2. 蝴蝶的強弱主要是來自於大小(字串的長度),長度長則強度越強;若長度一樣則比較字典序,字典序越大則越強。

註:字元的比較是 case sensitive,大小寫是為不同,aA 為不同字元。

但是,這座蝴蝶村莊中也有一些神奇蝴蝶,這類的蝴蝶整隻看起來未必是對稱的,原因是他是由一隻本體蝴蝶藉由偽裝術而成的。而本體蝴蝶和其他一般蝴蝶一樣,具有對稱的性質,並且該本體蝴蝶不能藉由偽裝術形成更強大的蝴蝶,即所有 神奇蝴蝶 之中可能的蝴蝶,本體蝴蝶是最強的那隻。

Input Format

輸入第一行有一個整數 $T$,代表測試資料的筆數。
接下來每行有一個字串 $s$,代表 彥人 看到的神奇蝴蝶。

$0 < T \le 20$
$0 < |s| \le 5000$

Output Format

對於每筆測試資料,請輸出一個整數,代表該神奇蝴蝶的本體蝴蝶的大小(字串的長度)。

Sample Input

3
pppmeowoemqqq
poOwuwOoq
orzzzz

Sample Output

7
7
4

Hints

  • 對於第一筆測試資料,其本體蝴蝶是 meowoem
  • 對於第二筆測試資料,其本體蝴蝶是 oOwuwOo
  • 對於第三筆測試資料,其本體蝴蝶是 zzzz

Problem Source

Subtasks

No. Testdata Range Score
1 0 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1