问题描述

新格尔公司的天才程序员菜哭武有很多猫，并且我们都知道他给他养的每一只猫都叫做“狗子”。但是“狗子”实在是太多了，终于有一天菜哭武想起来要给每一只“狗子”都取上名字了。于是菜哭武花了 209 秒钟按照他对“狗子”们的喜爱程度给所有的“狗子”取了不同的名字，每个名字由 1 到 20 个小写字母组成。其中，字典序越低代表这只“狗子”越被菜哭武宠爱。然后菜哭武把这些名字按顺序存到了一个列表里。

有一天，菜哭武的队友张老师和石头看到了这个列表，由于菜哭武每天不是写作业就是和“狗子”们玩，导致都没有时间陪队友们训练。于是张老师和石头为了提高整个队伍的纪律性，就偷偷的打乱了这个列表，并且连每只“狗子”的名字也打乱了顺序。第二天，菜哭武起床后像往常一样点开了列表，然后他哭了。

天才程序员菜哭武自然是可以重新排好顺序的，但是他现在在哭，没心情做这件事。请聪明的你根据这张被打乱的列表，告诉菜哭武每一只“狗子”被打乱前的宠爱排名最高可能是多少以及最低可能是多少。

输入格式

题目包含多组数据。

第一行一个整数 $T$，表示有 $T$ 组测试数据。($T \leq 5$)

对于每组数据分为 $N + 1$ 行：

第 1 行，一个正整数 $N$。代表“狗子”的数量。($1 \leq N \leq 50\,000$)

第 2 行至第 $N + 1$ 行，每行包含一个字符串代表“狗子”的名字（打乱后的）。每个字符串长度小于等于 20，且不为空。

输出格式

对于每组数据，第一行输出 Case #x:（$x$ 编号从 1 开始）。

第 2 到第 $N + 1$ 行，每行两个整数，代表列表中这只“狗子”的最高可能排名以及最低可能排名。

样例输入

1
5
gege
d
dddddd
ef
yzyyz

样例输出

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

提示

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