Longest Common Subsequence

It is a classic exercise - no idea why we were lacking it until now!

Common subsequence is like common substring, but letters don't need to be adjacent, though order should be kept. For example words banana and atanek have common substring an but common subsequence is aan.

Input data provides a T - number of testcases in the first line.
Then T lines follow, each containing some string of small latin letters.

Answer should for every test string give the length of the longest common subsequence between this string and its reverse.

Example

input data:
5
afzqo
wmfafmhu
bnkdqkdefjp
doambxhttgbofe
uqoydupcewmprbjw

answer:
1 5 3 6 3