Longest Weird Subsequence

All submissions for this problem are available.
Finding the longest increasing subsequence is an old and wellknown problem now. Here you will have to do something similar. You need to find the longest weird subsequence (LWS) of the given string. The subsequence is called weird if it can be split into two disjoint subsequences, one of which is nondecreasing and the other one is nonincreasing.
Just for clarity, by subsequence of the given string S we mean any string that can be obtained from S by erasing from it zero or more characters. So empty string is a subsequence of any string and any string is a subsequence of itself. Further, note that we consider only strings composed of lowercase Latin letters and these letters compared by their ASCII codes. So, for example, 'a' is smaller than 'b' and 'p' is larger than 'h'.
Now let's consider some example. Let S="aabcazcczba". Then "abczz" is its some nondecreasing subsequene, "zccb" is its some nonincreasing subsequence and "aabczcczba" is its some weird subsequence since it can be split into nondecreasing subsequence "aabzz" and nonincreasing subsequence "cccba": "AABcZccZba" (first subsequence is shown by capital letters just for calrity).
Input
The first line contains a single positive integer T, the number of test cases. T test cases follow. The only line of each test case contains a nonempty string S composed of lowercase Latin letters.
Output
For every test case, output the length of the LWS of the given string.
Constraints
1 ≤ T ≤ 10 1 ≤ length of S ≤ 2000
Example
Input 3 abc cbazyzabc ddaabbaacc Output 3 6 10
Explanation
First case: The string itself is LWS since it can be split into nondecreasing subsequence "abc" and nonincreasing empty subsequence.
Second case: One of the possible LWS is "cbaabc" since it can be split as "cbaABC". Here we indicate by capital letters nondecreasing subsequence and by lowercase letters nonincreasing one. Other possible LWS's are "cbaZZa", "AzyaBC".
Third case: Here the desired splitting is "ddAABBaaCC".
Author:  vamsi_kavala 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/LWS 
Tags  easy march12 vamsi_kavala 
Date Added:  29072011 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
Can an empty string be
@shadow: Yes, thus the answer
in 3rd case ddAABBaaCC ddBBaa
@ashmish2 : They need to be
@admin LWS for second case
@ashmish2: Please do not
some other test cases please
@admin One tricky test case,
will O(n*n) pass ??
@manoharsingh23: Please do
@vamsi_adm : i regret if i
@manoharsingh23: Yeah, you
@admin Hey! my code is
an somebody tell meaning of
Query: Anybody noticed that
@mpossible: I guess disjoint
@vamsi_adm : can there be
@nikku: No.
over and over i'm getting
i m getting "wrong
@vector9x and palak_agarwal:
So, contest ends. can someone