Description

As stated, given $N$ strings (the length of the $i$-th string is $M_i$, and each string contains digits and letters in both cases; it is case-sensitive), find how many distinct strings there are among the $N$ strings.

Friendly reminder: if you really want to practice hashing seriously, please be self-disciplined.

Input Format

The first line contains an integer $N$, the number of strings.

The next $N$ lines each contain one string, the provided strings.

Output Format

Output one line containing one integer, the number of distinct strings.

5
abc
aaaa
abc
abcc
12345

4

Hint

Constraints

For $30\%$ of the testdata: $N \leq 10$, $M_i \approx 6$, $M_{\max} \leq 15$.

For $70\%$ of the testdata: $N \leq 1000$, $M_i \approx 100$, $M_{\max} \leq 150$.

For $100\%$ of the testdata: $N \leq 10000$, $M_i \approx 1000$, $M_{\max} \leq 1500$.

Sample Explanation

In the sample, the first string $\tt{abc}$ and the third string $\tt{abc}$ are the same, so the set of provided strings is $\{\tt{aaaa}, \tt{abc}, \tt{abcc}, \tt{12345}\}$, hence there are $4$ distinct strings.

Further Reading

The following problems reflect the correctness analysis of string hashing from different aspects.

• P12197 Hash Killer I
• P12198 Hash Killer II
• P12199 (currently unsolved) Hash Killer III
• P12200 Hash Killer Extra
• P12201 Hash Killer Phantasm
• P7350 「MCOI-04」Dream and Strings

Translated by ChatGPT 5