A deck of alphabet cards contains cards marked with letters of the alphabet (A,B,C,…). Each letter appears on one or more cards. The pack is shuffled and the cards dealt out one by one into a number of stacks. Any number of stacks may be used, but after all the cards have been dealt, you must get all the cards into alphabetical order, with all cards showing A first and then all cards showing B and so on. Since they are stacked, only the top card of any stack can be retrieved.
Given the order of the cards, the objective is to determine the minimum number of stacks which enables the final operation of getting them into alphabetic order.
For example, if the order of the cards is ABNJJBBA, the stacks after dealing could be
AA, BBB, NJJ
It is obvious that this can be achieved during the dealing process. During the retrieval process, all the A’s can be picked up from stack 1 one at a time, by accessing only the top of the stack, all the B’s can be obtained in the same way, and then the J’s. Once the J’s have been picked up, the N’s are on top of the stack and can be picked up.
Input Format:
One line containing an integer N that defines how many sequences appear in this test case.
After the first line, N lines, each containing a sequence of space separated upper case letters. Note that not all letters need to be present, and that a letter may appear many times
Output Format:
N lines, each containing one integer representing the number of stacks needed for the corresponding sequence of cards in the input
Constraints:
1≤N≤20
Numbers of cards in each sequence ≤100