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 darkkcyan, very similar to the initial nickname, only duplication the 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 darkkcyan, ddarkcyan and darkcyann, and with three operations the nicknames ddaarrkcyan, darkkkkcyan or ddarkkcyann can be generated.

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