题目描述

商店出售 $N$ 种冰淇淋口味，第 $i$ 种口味由字符串 $F_i$ 表示。

购买一杯冰淇淋时，顾客选择一个非空字符串 $s$，这一杯会包含所有名称以 $s$ 为前缀的口味。

对于每个 $k=1,2,\ldots,N$，Filippo 希望恰好买到前 $k$ 种口味

而不能买到 $F_k,F_{k+1},\ldots,F_{N-1}$。同一种口味可以被多杯重复包含，但仍只算一种口味。

求每个 $k$ 所需杯数的最小值。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行一个字符串 $F_i$。

输出格式

输出 $N$ 行。第 $k$ 行表示恰好购买前 $k$ 种口味所需的最少杯数。

数据范围

• $2\le N\le100000$；
• 字符串仅包含小写英文字母；
• 所有字符串总长度不超过 $2000000$；
• 所有口味名称互不相同；
• 保证对每个 $k$ 都存在合法购买方案。

子任务

样例 1

输入
5
chocolate
coffee
cookies
pistachio
strawberry

输出
1
2
1
2
3

样例 2

输入
10
orange
peanutbutter
mango
mint
cheesecacke
coconut
oreo
cherry
peppermint
watermelon

输出
1
2
3
3
4
5
5
4
4
5