Longest Alphabetical Subsequence

Given a string s, your task is to find the length of the longest subsequence (not necessarily contiguous) in which all characters are unique and appear in strictly increasing alphabetical order.

A subsequence is obtained by deleting zero or more characters from the string without changing the order of the remaining characters.

For example, if s = "abcpqrabc", one of the longest valid subsequences is "abcpqr" which has a length of 6.

Note: The subsequence must be strictly increasing, i.e. for any two consecutive characters c1 and c2 in the subsequence, it must hold that \( c1 < c2 \) in lexical order.

inputFormat

The input begins with an integer T (\(T \ge 1\)) representing the number of test cases. Each of the next T lines contains a string s. The string may be empty.

outputFormat

For each test case, print a single integer on a new line representing the length of the longest alphabetical subsequence in the given string.

## sample

8
abcpqrabc
edcba
abcdefghijklmn
aabbcc
zyx
ace

abcdefghijklmnopqrstuvwxyz

6
1
14
3
1
3
0
26

</p>