Trie 是一种用于存储字符串的树形数据结构。以下是 Little Rabbit 用于在 Trie 中插入和查询字符串的 C++ 代码。字符集为小写字母。

struct Trie {
    int e[N][26], val[N], tot; // N 是一个常量
    Trie() {
        tot = 0;
        val[0] = Rand(1, 1000000000);
        memset(e, 0, sizeof e);
    }
    void insert(const char *s, int n) { // n 是字符串 s 的长度
        for (int i = 0, u = 0; i < n; u = e[u][s[i] - 'a'], i++)
            if (!e[u][s[i] - 'a']) {
                e[u][s[i] - 'a'] = ++tot;
                val[tot] = Rand(1, 1000000000);
                // Rand(l, r) 可以生成
                // [l, r] 范围内的不同随机数
            }
    }
    int query(const char *s, int n) { // n 是字符串 s 的长度
        int u = 0;
        for (int i = 0; i < n; u = e[u][s[i] - 'a'], i++)
            if (!e[u][s[i] - 'a'])
                break;
        return val[u];
    }
};

请注意，Rand 函数生成的整数都是互不相同的。

Little Rabbit 使用 insert 函数在 Trie 中插入了一些（可能为零个）字符串。但过了一段时间，他完全忘记了插入的字符串。于是他使用 query 函数查询了 $n$ 次字符串，并得到了 $n$ 个返回值。根据这些返回值，你需要告诉 Little Rabbit 该 Trie 至少有多少个节点。请注意，Trie 的根节点也应计为一个节点。在上述代码中，节点总数为 tot + 1。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5000$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示 Little Rabbit 使用 query 函数的次数。

接下来的 $n$ 行，每行包含一个仅由小写字母组成的字符串 $s$ 和一个整数 $v$ ($1 \le v \le 10^9$)，表示 Little Rabbit 查询字符串 $s$ 得到的返回值为 $v$。每个测试用例中字符串长度之和不超过 $10^5$，所有测试用例中字符串长度之和不超过 $5 \times 10^5$。

输出格式

对于第 $x$ 个测试用例，如果答案为 $y$，则在一行中输出 Case #x: y。如果不存在满足条件的 Trie，则在一行中输出 Case #x: -1。

样例

输入 1

6
2
aa 1
a 2
1
a 1
3
aa 1
ab 1
ac 1
2
aa 1
ac 2
3
aaa 1
ac 1
aa 3
3
aa 1
ac 1
a 3

输出 1

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