Lộc likes dark cyan, because of that, when Lộc registers his first
account on a mysterious Online Judge, he chose the nickname `darkcyan`

.
Unfortunately, this nickname was taken. The system recommends Lộc a
couple of other nicknames, some of which are `darkcyan_no1`

,
`darkcyan_pro`

and `darkcyan_vip`

, none of which Lộc liked at all. After
spending a few eternities pondering, the nickname chosen by Lộc was
`dar`

, very similar to the initial nickname, only duplication the
__kk__cyan`k`

. This nickname turns out wasn't taken! So it became Lộc's new
nickname for many other different Online Judges.

Lộc finds changing nicknames like this interesting, and he applies this idea to create an entirely novel nickname suggestion system! For a nickname that's represented by a string with ~k~ characters ~t_1 t_2 \ldots t_k~, the system can change the nickname using the following operation several (possibly zero) times:

- The system selects an integer ~i~ (~1 \le i \le k~), then inserts the character ~t_i~ right after position ~i~. The new character's index is ~i + 1~ and the index of every following characters are increased by one. The length of the new nickname will be ~k + 1~.

For example, given the nickname `darkcyan`

, with one operation, the
system can generate the nicknames `dar`

, __kk__cyan

and
__dd__arkcyan`darkcya`

, and with three operations the nicknames __nn__

, __ddaarr__kcyan`dar`

or __kkkk__cyan

can be generated.__dd__ar__kk__cya__nn__

For the sake of optimization, the system needs to use the least operations to change a nickname, such that the nickname has never appeared in the system, to recommend for the user.

Lộc thinks it's a pity if there's no existing nickname recommendation
system like this. So he decides to implement this system for the social
network *Virtual Network for Online Intercommunication* (VNOI) that he's
developing. On VNOI there are currently ~n~ users, the ~i~-th of which
has the nickname ~S_i~. Lộc wants to know, for each nickname ~S_i~, if
there is a new user who attempts to register with this nickname, how
many operations does it take for this system to generate a new, unused
username on VNOI. As Lộc is a very busy developer, he needs your help to
solve this problem.

Given the list of nicknames of the ~n~ users on the system, for each nickname ~S_i~, calculate the least number of operations to turn ~S_i~ into a new, unused nickname, on the system.

#### Input

The first line contains an integer ~n~ (~1 \le n \le 10^6~) the number of VNOI users.

The ~i~-th line out of the next ~n~ lines contains a single string ~S_i~ (~1 \le |S_i| \le 10^6~, ~S_i~ consists only of lowercase English letters), the nickname of the ~i~-th user.

The total length of all the nicknames do not exceed ~10^6~. Furthermore, no two nicknames are the same.

#### Output

Output ~n~ lines. The ~i~-th of which denoting the least number of steps to turn ~S_i~ into a nickname that has not appeared on the system.

#### Scoring

Subtask 1 (~55~ points): All the characters within one nickname are the same.

Subtask 2 (~75~ points): No additional constraints.

The total score for this problem is ~130~.

#### Sample Input 1

```
3
aaa
a
aa
```

#### Sample Output 1

```
1
3
2
```

#### Sample Input 2

```
3
ab
aab
abb
```

#### Sample Output 2

```
2
1
1
```

## Comments