Problem 1113. -- 菜哭武的猫

1113: 菜哭武的猫

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 172  Solved: 33
[Submit][Status][Web Board]

Description

新格尔公司的天才程序员菜哭武有很多猫,并且我们都知道他给他养的每一只猫都叫做“狗子”。但是“狗子”实在是太多了,终于有一天菜哭武想起来要给每一只“狗子”都取上名字了。于是菜哭武花了209秒钟按照他对“狗子”们的喜爱程度给所有的“狗子”取了不同的名字,每个名字由1到20个小写字母组成。其中,字典序越低代表这只“狗子”越被菜哭武宠爱。然后菜哭武把这些名字按顺序存到了一个列表里。
有一天,菜哭武的队友张老师和石头看到了这个列表,由于菜哭武每天不是写作业就是和“狗子”们玩,导致都没有时间陪队友们训练。于是张老师和石头为了提高整个队伍的纪律性,就偷偷的打乱了这个列表,并且连每只“狗子”的名字也打乱了顺序。第二天,菜哭武起床后像往常一样点开了列表,然后他哭了。
天才程序员菜哭武自然是可以重新排好顺序的,但是他现在在哭,没心情做这件事。请聪明的你根据这张被打乱的列表,告诉菜哭武每一只“狗子”被打乱前的宠爱排名最高可能是多少以及最低可能是多少。

Input

题目包含多组数据。
第一行一个整数T,表示有T组测试数据。(T ≤ 5)
对于每组数据分为N+1行:
第1行,一个正整数N。代表“狗子”的数量。(1 N 50, 000)
第2行至N+1行,每行包含一个字符串代表“狗子”的名字(打乱后的)。每个字符串长度小于等于20,且不为空。

Output

对于每组数据,第一行输出Case #x: (x编号从1开始)
第2到第N+1行,每行两个整数,代表列表中这只“狗子”的最高可能排名以及最低可能排名。

Sample Input

1
5
gege
d
dddddd
ef
yzyyz

Sample Output

Case #1:
3 4
1 1
2 2
3 4
5 5

HINT

d、dddddd、yzyyz无论原来的字符顺序是什么,它们的排名都不会改变,分别是1、2、5。而gege、ef,例如gege的原顺序为eegg,ef的原顺序为ef,则eegg排第三;当gege的原顺序为ggee,ef的原顺序为ef,则ggee排第四。所以第1只“狗子”可能的最高以及最低排名为3和4。同理,第四只“狗子”的输出为3和4。

Source

[Submit][Status]