407522: GYM102822 C Code a Trie

A Trie is a tree data structure used to store strings. Here is Little Rabbit's C++ code for inserting and querying a string in a Trie. The character set is lowercase letters.

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[s[i] - 'a'], i++)
            if (!e[s[i] - 'a']) {
                e[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[s[i] - 'a'], i++)
            if (!e[s[i] - 'a'])
                break;
        return val;
    }
};

Please note that the integers generated by $$$Rand$$$ function are all distinct.

Little Rabbit inserts some (possibly zero) strings in the Trie by using the $$$insert$$$ function. But after a while, he totally forgets those strings he has inserted. So he uses the $$$query$$$ function $$$n$$$ times to query some strings and gets $$$n$$$ return values. According to these values, you need to tell Little Rabbit how many nodes the Trie has at least. Please note that the root of the Trie should also be counted as a node. In the code above, the number of nodes is $$$\text{tot}+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

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