0173 - 階層民主主義

デモクラティア共和国の大統領は，以下のような複数段階の選挙により選ばれる．

1. 大統領選挙の候補者は2名である．
2. 第1段階の選挙では，有権者は選挙区ごとに投票する．有権者の過半数の票を得た候補者がその選挙区の勝者となる．有権者が投票するのはこの第1段階だけである．
3. 第k段階 (k > 1) の選挙区は，複数の第k − 1段階の選挙区を含む．一方，第k − 1段階の各選挙区は，ちょうど一つの第k段階の選挙区に含まれる．そして，第k段階の選挙区の勝者は，この選挙区に含まれる第k − 1段階の選挙区のうち過半数で勝った候補者である．
4. 最終段階の選挙区は全国区であり一つしかない．ここでの勝者が大統領に選ばれる．

この国の大統領選挙では，以下の仮定が成り立つ．

• すべての有権者が，それぞれ一票を投じる．
• 第1段階の各選挙区の有権者数は奇数である．
• 第k段階 (k >1) の各選挙区に含まれる第k − 1段階の選挙区の数も奇数である．

したがって，すべての段階のすべての選挙区で，必ずどちらかの候補が勝つ (引き分けはない)．

あなたの仕事は，なるべく少ない得票数で大統領選挙に勝つ方法を求めるプログラムを作成することである． たとえば，最終段階の選挙区がちょうど三つの第1段階の選挙区を含んでおり，これらの第1段階の選挙区の有権者数がそれぞれ123名，4567名，89名だったとする． この場合，最初の選挙区で62票，3番目の選挙区で45票の計107票を獲得するのが，最も少ない得票数で勝つ方法になる． この場合，仮にもう一人の候補が2番目の選挙区で4567票すべてを獲得したとしても，敗者となることは避けられない． 不公平な選挙制度だと思うかもしれないが，これも現実として受け止めて欲しい．

入力全体は以下の形式をしている．

データセット数(=n)
データセット1の記述
データセット2の記述
…
データセットnの記述

データセット数nは100以下である．

各選挙区の有権者数と選挙区同士の関係を次のような書式で記す．

• 第1段階の各選挙区は，[c]と記す．ただし，cはその選挙区の有権者数である．
• 第k段階(k > 1)の各選挙区は，[d₁d₂…d_m]と記す．ただし，d₁, d₂, …, d_mは，この選挙区に含まれる第k − 1段階の各選挙区をこの書式にしたがって記したものである．

たとえば，有権者数123名の第1段階の選挙区は，[123]と記される． また，有権者数がそれぞれ123名，4567名，89名の三つの第1段階の選挙区を含む第2段階の選挙区は，[[123][4567][89]]と記される．

各データセットは1行であり，この行は，最終段階の選挙区を上の書式で記した文字列よりなる． この問題を解くにあたり，次のように仮定して良い．

• 各データセットの文字列は数字('0', '1', …, '9')と角括弧('[', ']')以外の文字を含まず，その長さは11以上10000以下である．
• 第1段階の各選挙区の有権者数は3名以上9999名以下である．

ステージの段数は国全体で一定である． したがって，たとえば，[[[9][9][9]][9][9]] は決して入力に現れない． また，[[[[9]]]] も現れない． なぜならば，第2段階以降の選挙区は，一つ前の段階の選挙区を必ず複数含むからである．

各データセットに対し，最少得票数で大統領選挙に勝つために必要な票数を求め，それを1行に出力しなさい． 各出力行はこの数値以外の文字を含んではならない．

6
[[123][4567][89]]
[[5][3][7][3][9]]
[[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]
[[[37][95][31][77][15]][[43][5][5][5][85]][[71][3][51][89][29]][[57][95][5][69][31]][[99][59][65][73][31]]]
[[[[9][7][3]][[3][5][7]][[7][9][5]]][[[9][9][3]][[5][9][9]][[7][7][3]]][[[5][9][7]][[3][9][3]][[9][5][5]]]]
[[8231][3721][203][3271][8843]]

107
7
175
95
21
3599