Cho một xâu ký tự ~st~ chỉ gồm các chữ cái Alphabet in thường. Bạn có quyền bỏ bớt hoặc hoán đổi vị trị các ký tự để được một xâu đối xứng hay còn gọi là xâu Palindrome.

Hãy tìm ra độ dài lớn nhất của xâu đối xứng có thể đạt được.

Input

Dòng đầu tiên chứa ~T~ là số lượng testcase thỏa ~T \le 10~.

~T~ dòng tiếp theo, mỗi dòng chứa xâu ~st~ cần xử lý và tính.

Output

In ra kết quả của các testcase, mỗi kết quả in trên một dòng.

Samples

Sample Input 1

2
abc
aab

Sample Output 1

1
3