{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cimg src\u003d\"CDN_BASE_URL/ef457d9ef03c54dabae4fb3c7cc49d9e?v\u003d1714347794\" border\u003d\"0\" alt\u003d\"Problem illustration\" align\u003d\"RIGHT\" class\u003d\"problem_raimage\"\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eMisha has an old Nokia and many friends, so many that it takes a lot of \r\ntime to find a phone number. \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe friends\u0027 names in the phonebook are ordered alphabetically. Passing \r\nfrom a phone number to the next number on the list is done by pressing the \r\n`down\u0027 button, and passing to the preceding number is done by pressing the \r\n`up\u0027 button. The list is cyclic, which means that pressing the `up\u0027 button \r\nat the first name in the list takes Misha to the last name and pressing \r\nthe `down\u0027 button at the last name takes him to the first name. \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eWhen Misha opens the phonebook, he can see the names of all his friends, \r\nand the current name is the alphabetically first name. If he starts typing \r\nsome word on the phone\u0027s keyboard, the phone will show only the names \r\nstarting with the typed sequence of letters. In this case, the current \r\nname will be the name that alphabetically precedes the other names. If the \r\nlast of the typed letters is deleted, then all the names starting with the \r\nshorter sequence of letters become available but the current name remains \r\nthe same. If all the letters are deleted, then the current name remains \r\nthe same and all the entries in the phonebook become available. If the \r\nsequence that should appear after pressing a button is not a beginning of \r\nany name in the phonebook, the phone will produce an unpleasant sound and \r\nthe typed letter will not appear on the screen. \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003ePressing one button takes exactly one second. The first letter on a button \r\nis typed in one pressing, the second letter is typed in two pressings, and \r\nso on. The keyboard looks as follows:\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_center\"\u003e\u003ctable\u003e\r\n\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003e\r\n\u003c/td\u003e\u003ctd\u003eabc\u003c/td\u003e\u003ctd\u003edef\r\n\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\r\nghi\u003c/td\u003e\u003ctd\u003ejkl\u003c/td\u003e\u003ctd\u003emno\r\n\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\r\npqrs\u003c/td\u003e\u003ctd\u003etuv\u003c/td\u003e\u003ctd\u003ewxyz\r\n\u003c/td\u003e\u003c/tr\u003e\r\n\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eYou are given a list of Misha\u0027s friends. For each name calculate the time \r\nin which Misha can choose this name in the list. \u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains the number \u003ci\u003en\u003c/i\u003e of entries in Misha\u0027s phonebook (1 \r\n≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e). In each of the following \u003ci\u003en\u003c/i\u003e lines you are given a \r\nnonempty word consisting of lowercase English letters. The words are \r\nordered alphabetically. All the entries in the phonebook are different. \r\nThe total length of the words does not exceed\u0026nbsp;10\u003csup\u003e5\u003c/sup\u003e. \u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput \u003ci\u003en\u003c/i\u003e integers separated with a space. The \u003ci\u003ei\u003c/i\u003eth integer must be the \r\nminimum time in which the \u003ci\u003ei\u003c/i\u003eth name can be chosen. \u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\na\r\naaa\r\naab\r\nb\r\nd\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 1 2 2 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}