Ієрархічна демократія
Президентські вибори в Республіці Демократія проходять у кілька етапів за наступною схемою:
Є рівно два кандидати на пост президента.
На першому етапі виборці, які мають право голосу, голосують на виборчих дільницях свого округу. Переможцем округу стає кандидат, який отримує більшість голосів. Голосування відбувається лише на цьому першому етапі.
Округ k-го етапу (k > 1) складається з кількох округів (k−1)-го етапу. Округ (k−1)-го етапу є підокругом одного і тільки одного округу k-го етапу. Переможцем округу k-го етапу стає кандидат, який перемагає в більшості своїх підокругів (k−1)-го етапу.
Останній етап має лише один загальнонаціональний округ. Переможець останнього етапу стає президентом.
Можна припустити наступне щодо президентських виборів у цій країні:
Кожен виборець, який має право голосу, голосує.
Кількість виборців, які мають право голосу, у кожному виборчому окрузі першого етапу є непарною.
Кількість підокругів (k−1)-го етапу, які складають округ k-го етапу (k > 1), також є непарною.
Це означає, що кожен округ кожного етапу має свого переможця (немає нічиєї).
Ваше завдання — написати програму, яка визначить, як виграти президентські вибори з мінімальною кількістю голосів. Наприклад, якщо округ останнього етапу має три підокруги першого етапу, і кількість виборців у підокругах становить 123, 4567 і 89 відповідно, то мінімальна кількість голосів, необхідна для перемоги, становить 107, тобто 62 з першого округу і 45 з третього. У цьому випадку, навіть якщо іншому кандидату віддати всі 4567 голосів у другому окрузі, він/вона неминуче програє. Хоча ця виборча система може здаватися несправедливою, ви повинні прийняти її як реальність.
Вхідні дані
Вхідні дані мають такий вигляд:
кількість наборів даних (=n)
1-й набір даних
2-й набір даних
…
n-й набір даних
Кількість наборів даних, n, не перевищує 100.
Кількість виборців, які мають право голосу, у кожному окрузі та відношення частина-ціле між округами позначаються наступним чином.
Виборчий округ першого етапу позначається як [c], де c — кількість виборців у окрузі.
Округ k-го етапу (k > 1) позначається як [d_1d_2…d_m], де d_1, d_2, …, d_m позначають його підокруги (k−1)-го етапу.
Наприклад, виборчий округ першого етапу, що має 123 виборців, позначається як [123]. Округ другого етапу, що складається з трьох підокругів першого етапу, які мають 123, 4567 і 89 виборців, позначається як [[123][4567][89]].
Кожен набір даних — це рядок, що містить символи, які позначають округ останнього етапу в зазначеному вище форматі. Можна припустити наступне:
Рядок символів у кожному наборі даних не містить жодних символів, окрім цифр ('0', '1', …, '9') і квадратних дужок ('[', ']'), а його довжина становить від 11 до 10000 включно.
Кількість виборців у кожному виборчому окрузі першого етапу становить від 3 до 9999 включно.
Кількість етапів є загальнонаціональною константою. Отже, наприклад, [[[9][9][9]][9][9]] ніколи не з'являється у вхідних даних. [[[[9]]]] також не може з'явитися, оскільки кожен округ другого або пізнішого етапу повинен мати кілька підокругів попереднього етапу.
Вихідні дані
Для кожного набору даних виведіть мінімальну кількість голосів, необхідну для перемоги на президентських виборах, у рядку. Жоден рядок виводу не може містити жодних символів, окрім цифр, якими записано число.