迴文字 (palindrome)，是一個英文單字的字母由左邊讀起，與從右邊讀起的順序是一樣的，例如：GAG, MADAM, ABCCBA，但是 ADAM 並非一個迴文字，在此我們將空字串也視為一個迴文字。
對於任一個單字，我們一定能藉由刪除部分字母使得單字變成迴文字，例如將 ADAM 中的 M 刪除後得到 ADA 為一個迴文字。
本題請你寫一個程式判斷一個單字藉由刪除部份字母後，得到一個迴文字的最長長度為何。
Input and Output
輸入的第一列有一個整數 $T$ ($\leq{60}$)。表示接下來有 $T$ 列，每列為一個長度少於 $1000$ 的字串。
對於大部份的字串 ($\geq{90}\%$) 其長度 $\leq{255}$。
請你輸出該字串變成一個迴文字的最大長度為何。
Sample Input
2
ADAM
MADAM
Sample Output
3
5