在一个字符串王国里面，只有字符串（字符串仅包含小写字母），每一个字符串都具有繁殖能力，它能繁殖出一个小的字符串，只要这个字符串满足是原字符串的子串。例如字符串ab可以繁殖出a、b、ab，它们称此为父子关系。但是，与地球不同的是，每个子串又无数个父串，因为它们认为，只要能繁殖出自己，那么对方与自己就是父子关系。例如，ab可以来自于aba、abaf、abc等等，所以对于ab而言，满足上述条件的都是它的父串，而一个父串它的子串是有限的。如果有以下串满足a是b的子串，b是c的子串，那么a->b->c就构成了一个类似族谱的东西，它们称之为串祖。当然，一个字符串也可以形成一个串祖。

每个字符串还会有一个价值标准（一个int范围内的整数），一次决定自己的社会地位（某个字符串可以将自己加入某一个串祖，然后计算一个串祖总的价值，以此来决定社会地位，例如a的价值是1，ab的价值是2，a加入ab的串祖后，整个串祖的价值就变成了1+2=3，随之a和ab的社会地位也会提升）。

现在给定一些个字符串和价值标准，你需要计算出给定的字符串中，按照先后顺序出现来排列，而形成的所有的串祖中社会地位最高的一个，即串祖的总价值最高的一个，并输出确定数值。

第一行一个整数T(1 <= T <= 50)，表示每组数据的测试样例个数

每组测试样例的第一行一个整数n(1≤n≤2000)

接下来n行，每行一个字符串s和一个数字number，表示字符串s的价值为number。

每组测试样例，输出一行”Case #K: D”（不含双引号），K表示测试样例的组数，从1开始，D表示当前 (第K组) 测试样例的结果。