Misha has an old Nokia and many friends, so many that it takes a lot of time to find a phone number.

The friends' names in the phonebook are ordered alphabetically. Passing from a phone number to the next number on the list is done by pressing the `down' button, and passing to the preceding number is done by pressing the `up' button. The list is cyclic, which means that pressing the `up' button at the first name in the list takes Misha to the last name and pressing the `down' button at the last name takes him to the first name.

When Misha opens the phonebook, he can see the names of all his friends, and the current name is the alphabetically first name. If he starts typing some word on the phone's keyboard, the phone will show only the names starting with the typed sequence of letters. In this case, the current name will be the name that alphabetically precedes the other names. If the last of the typed letters is deleted, then all the names starting with the shorter sequence of letters become available but the current name remains the same. If all the letters are deleted, then the current name remains the same and all the entries in the phonebook become available. If the sequence that should appear after pressing a button is not a beginning of any name in the phonebook, the phone will produce an unpleasant sound and the typed letter will not appear on the screen.

Pressing one button takes exactly one second. The first letter on a button is typed in one pressing, the second letter is typed in two pressings, and so on. The keyboard looks as follows:

You are given a list of Misha's friends. For each name calculate the time in which Misha can choose this name in the list.

The first line contains the number n of entries in Misha's phonebook (1 ≤ n ≤ 10⁵). In each of the following n lines you are given a nonempty word consisting of lowercase English letters. The words are ordered alphabetically. All the entries in the phonebook are different. The total length of the words does not exceed 10⁵.

Output n integers separated with a space. The ith integer must be the minimum time in which the ith name can be chosen.