function contacts(queries: string[][]): number[] {
    const prefixMap = new Map<string, number>();
    const output: number[] = [];

    for (const element of queries) {
        switch (element[0]) {
            case "add":
                const word = element[1];
                for (let i = 1; i <= word.length; i++) {
                    const prefix = word.substring(0, i);
                    prefixMap.set(prefix, (prefixMap.get(prefix) || 0) + 1);
                }
                break;
            case "find":
                const prefix = element[1];
                output.push(prefixMap.get(prefix) || 0);
                break;
            default:
                break;
        }
    }

    return output;
}