Description

kkksc03 is an extraordinary dreamer! In a short time, he imagined a large number of web pages and always handed them to the poor lzn to implement.

On Luogu’s web frontend, there are many folders, and folders are nested inside folders.

For example: $\verb!/luogu/application/controller!$ means that under the root directory there is a folder named $\verb!luogu!$, inside which there is a folder named $\verb!application!$, and inside that there is a folder named $\verb!controller!$.

In each path, the $1$-st character is always $\verb!/!$, there are no two consecutive $\verb!/!$ characters, and the last character is not $\verb!/!$. All names contain only digits and lowercase letters.

Currently, the root directory is empty. kkksc03 has thought of many folder pathnames that should exist. The question is: to make all these folders exist, how many folders need to be newly created?

Input Format

The $1$-st line contains a positive integer $N$.

The next $N$ lines each contain a string describing a path, with length no more than $100$.

Output Format

The output should contain $N$ lines, each with a single positive integer. On the $i$-th line, output the minimum number of folders that need to be created so that the first $1$ through $i$ paths exist.

2
/luogu/application/controller
/luogu/application/view

3
4

3
/chicken
/chicken/egg
/chicken

1
2
2

4
/a
/a/b
/a/c
/b/b

1
2
3
5

Hint

Constraints

• For $20\%$ of the testdata, $N \le 20$.
• For $50\%$ of the testdata, $N \le 200$.
• Additionally, for $30\%$ of the testdata, every path contains at most two $\verb!/!$ characters (counting the first character).
• For all testdata, $N \le 1000$.

Translated by ChatGPT 5