Migrated from Lutece 2618 hard string problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

struct Trie {
    int e[N][26], val[N], tot; // N is a constant
    Trie() {
        tot = 0;
        val[0] = Rand(1, 1000000000);
        memset(e, 0, sizeof e);
    }
    void insert(const char *s, int n) { // n is the length of string 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) can generate
                // distinct random numbers in the range of [l, r]
            }
    }
    int query(const char *s, int n) { // n is the length of string 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];
    }
};

给出一棵用 insert 函数构造得来的 Trie。

现在你不知道树的形态，但是你知道你使用了 $n$ 次 query 函数，以及每一次调用的返回值。求这棵 Trie 最少有几个节点。

（注：$0$ 号节点也被认为是一个节点）

Input

第一行一个数字 $t$ 代表数据组数； 接下来 $t$ 组数据按以下格式输入： 第一行一个数字 $n$； 接下来 $n$ 行，每行一个由小写字母组成的字符串 $s$ 和一个数字 $p$； 代表输入字符串为 $s$ 时 query 的返回值为 $p$。

Output

对于每一组数据，输出格式为 printf("Case #%d: %d\n",case,ans)。

ans 为 trie 中的最少点数，当 Trie 不合法时输出 $-1$。

Samples

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

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

Resources

2021 UESTC ICPC Training for String and Search Algorithm