Иерархическая демократия
Президентские выборы в Республике Демократия проходят в несколько этапов следующим образом:
Участвуют ровно два кандидата в президенты.
На первом этапе избиратели голосуют на участках своего округа. Победителем округа становится кандидат, набравший большинство голосов. Голосование происходит только на этом этапе.
Округ 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]]]], так как каждый округ второго или более позднего этапа должен иметь несколько подокругов предыдущего этапа.
Выходные данные
Для каждого набора данных выведите минимальное количество голосов, необходимое для победы на президентских выборах, в строке. Ни одна строка вывода не должна содержать никаких символов, кроме цифр, представляющих число.