Вам заданий набір непустих рядків. Для кожного рядку потрібно порахувати суму кількості входжень його непустих префіксів у набір.

Розглянемо на прикладі. ["abc", "ab", "bc", "b"]. Перший рядок складається із наступних префіксів: "a", "ab", "abc". Префікс "a" є префіксом 2 рядків із набору (першого і другого), "ab" також 2, "abc" є префіксом тільки одного рядку - першого. Тому відповідь для першого рядку складає 2+2+1=5.

Input

На вхід користувачу приходить один рядок із набором. Набір починається символом '[' та закінчується символом ']'. Кожен рядок в наборі загорнутий символами " (подвійними лапками). Рядки розділені комою. Кількість рядків у наборі не перевищує 1000. Рядки непорожні та складаються із не більше 1000 малих латинських символів.

Output

Вивести необхідно стільки чисел, скільки рядків у вхідному наборі. Числа вивести в одному рядку через пробіл.

Sample Input 1

["abc","ab","bc","b"]

Sample Output 1

5 4 3 2