Yêu cầu, cài đặt bằng hai cách: Đệ quy có nhớ và quy hoạch động với mảng hai chiều

Một xâu được gọi là đối xứng, nếu đọc từ trái qua phải cũng như đọc từ phải qua trái. Ví dụ, xâu "GAG" và "MADAM" được gọi là những xâu đối xứng, nhưng "ADAM" lại không được gọi là xâu đối xứng. Ta quan nhiệm một xâu rỗng được gọi là một xâu đối xứng.

Từ bất kỳ một xâu không đối xứng nào, bạn luôn luôn có cách để loại bỏ một số kí tự, để thu được một xâu đối xứng. 

Ví dụ, cho xâu ADAM, ta có thể xóa kí tự M và thu được xâu đối xứng là ADA.

Viết một chương trình để xác định xem chiều dài của xâu đối xứng dài nhất có thể thu được bằng cách xóa đi không, một, hoặc một vài kí tự từ xâu đã cho 

Input:

Dòng đầu tiên gồm số nguyên dương T (T<=60), đó là số test.

Mỗi dòng trong T dòng tiếp theo gồm một xâu, mà chiều dài của xâu đó luôn luôn nhỏ hơn hoặc bằng 1000.

Ouput:

Với mỗi xâu Input, đưa ra chiều dài của của xâu đối xứng dài nhất, thu được bằng cách xóa đi không hoặc một vài kí tự từ xâu đã cho.