11151 - Longest Palindrome

迴文字(palindrome)，是一個英文單字的字母由左邊讀起，與從右邊讀起的順序是一樣的，例如：GAG, MADAM, ABCCBA，但是ADAM並非一個迴文字，在此我們將空字串也視為一個迴文字。
對於任一個單字，我們一定能藉由刪除部分字母使得單字變成迴文字，例如將ADAM中的M刪除後得到ADA為一個迴文字。
本題請你寫一個程式判斷一個單字藉由刪除部份字母後，得到一個迴文字的最長長度為何。

Input and Output

輸入的第一列有一個整數T(<= 60)。表示接下來有T列，每列為一個長度少於1000的字串。
對於大部份的字串(>= 90%)其長度<=255。
請你輸出該字串變成一個迴文字的最大長度為何。

Sample Input

2
ADAM
MADAM

Sample Output

3
5

---

原文出處