在接下来的 $n$ 天里，一个新网站将发布 $n$ 款网页游戏。根据计划，管理员每天会发布一款新游戏。用户必须打开相应的 URL（统一资源定位符）并从服务器获取反馈来下载游戏。

然而，服务器的设置使用了难以理解的遗留代码。一旦用户以某种方式找到了未发布游戏的 URL，游戏数据就会泄露。为了临时解决这个问题，管理员决定在服务器端添加一系列“确认前缀”（confirmation prefixes），它们是非空字符串。当请求的 URL 对应于某款游戏（无论是否已发布）且至少有一个确认前缀是该 URL 的前缀时，服务器将返回正确的游戏数据；否则，服务器将声明找不到该游戏。

为了简化工作，管理员请你计算在每次发布新游戏后，为避免数据泄露，服务器所需的最少确认前缀数量。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^4$)，表示将要发布的游戏数量。

接下来的 $n$ 行中，第 $i$ 行包含一个非空字符串，仅由小写字母（'a' 到 'z'）、点（'.'）和斜杠（'/'）组成，表示第 $i$ 天发布的游戏的 URL。

保证每个给定 URL 的长度最多为 50，且没有任何给定的 URL 是其他任何给定 URL 的前缀。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数，表示在第 $i$ 款新游戏发布后，所需的最少确认前缀数量。

样例

输入 1

3
ufoipv.ofu
hsbocmvfgboubtz.kq
hfotijo.njipzp.dpn/kb

输出 1

1
2
2