Problem Description

题目描述

Moist has a hobby: collecting figure skating trading cards. His collection has grown so large that it is difficult to keep it in one disorganized pile. He wants the cards sorted alphabetically so he can find them quickly.

The cards are difficult to handle, so Moist uses a sorting robot. The robot scans the deck from top to bottom. Whenever it finds a card whose name is lexicographically smaller than the preceding card, it moves that card to its correct place among the cards already scanned. Each such move costs one dollar.

Determine the total cost of sorting the deck.

输入格式

The first line contains an integer $T$, the number of test cases. Each test case begins with an integer $N$, followed by $N$ lines, each containing one skater's name in the deck's original order.

输出格式

For each test case, output one line in the format "Case #x: y", where $x$ is the 1-based case number and $y$ is the total cost in dollars.

样例

样例 1

提示

Limits: $1\le T\le100$, $1\le N\le100$. Each name has at most 100 characters and contains only English letters and spaces; names do not begin or end with spaces and are unique within a test case. Lexicographic order is space, uppercase letters, then lowercase letters.

2
2
Oksana Baiul
Michelle Kwan
3
Elvis Stojko
Evgeni Plushenko
Kristi Yamaguchi

Case #1: 1
Case #2: 0