Moist's Card Sorting

Moist collects figure skating trading cards. The collection has grown too large to keep in one messy pile, so he wants the deck sorted in lexicographic order from top to bottom, ready for the moment he needs a particular card.

The trouble is that Moist cannot pick up the cards himself. They slide out of his hands, and the sweat damages them permanently. Some of the cards are expensive. So Moist talked Dr. Horrible into building him a sorting robot. In Dr. Horrible's usual style, the robot charges Moist $1 every time it moves a card.

The robot's sorting mechanism is primitive. It scans the deck from top to bottom. Whenever it finds a card that is lexicographically smaller than the card directly above it, the robot pulls that card out and inserts it at its correct place in the stack above, which costs $1. The robot then resumes scanning downward from where it stopped, and it repeats this until the whole deck is sorted lexicographically from top to bottom.

Moist is almost broke, and keeping the cards in order is the only thing he still enjoys. Work out how many dollars the robot charges to sort each deck.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N. The next N lines each contain the name of a figure skater, listed from the top of the deck to the bottom.

Limits

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 100.
• Each name consists only of letters and the space character.
• Each name contains at most 100 characters.
• No name starts or ends with a space.
• No name appears more than once in the same test case.
• In lexicographic order the space character comes first, then the uppercase letters, then the lowercase letters.

For each test case, print one line in the form "Case #x: y", where x is the test case number starting from 1 and y is the number of dollars the robot charges to sort that deck.