This is the day you have been waiting for! You have been shortlisted for an interview with an upcoming startup 'Tookitaki' which focuses on online advertising. You already know that there will be a question about LCS (Longest Common Subsequence). As you know the algorithm well you are pretty confident. But a surprise awaits you! The question asked by the interviewer turns out to be:

"Given a string S, find a string T of length equal to |S| such that LCS(S, T) <= LCS(S, G) holds for every string G of length equal to |S|. Print the length of LCS(S, T)."

INPUT:

The first line contains an integer N, the number of test cases. The following N lines each contain a string S consisting of lowercase 'a' to 'z' characters only.

OUTPUT:

For each test case print the required answer.

CONSTRAINTS:

1<= N < 100

|S| <= 500

PROBLEM SETTER: Shreyas Basarge