AT_bogosortcontest_div2_e Delete Sad Faces (Easy)

> AtCoder でレートが減少したときにポストをすると、 `:(` と表示されます。tatesoto 君はこれを見ると悲しくなってしまうので、tatesoto 君のために悲しい顔を消して、笑顔でいっぱいにしてあげてください。 文字 `:`, `(`, `)` からなる文字列について考えます。 隣接する $ 2 $ 文字が以下のいずれかであるとき、その $ 2 $ 文字を顔文字と呼びます。 - `:)`, `(:` を笑顔と呼びます。 - `:(`, `):` を悲しい顔と呼びます。 文字列 $ T $ に含まれる笑顔（悲しい顔）の個数とは、 $ 1 \le i \lt |T| $ を満たし、 $ T_iT_{i+1} $ が笑顔（悲しい顔）であるような整数 $ i $ の個数を指します。 複数の顔文字が同じ文字を共有している場合も、それぞれ数えることに注意してください。例えば、文字列 `(:):` には、`(:`, `:)`, `):` が含まれるため、笑顔の個数は $ 2 $ 、悲しい顔の個数は $ 1 $ です。 文字列 $ S $ が与えられます。 あなたは $ S $ に対して、以下の操作を悲しい顔が含まれなくなるまで繰り返します。 - 現在の文字列 $ S $ に含まれる悲しい顔を $ 1 $ つ選び、その $ 2 $ 文字を削除する。その後、残った文字を順番を変えずに詰める。 最終的な文字列 $ S $ に含まれる笑顔の個数としてあり得る最大値を求めてください。 $ T $ 個のテストケースについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ S $

各テストケースについて、答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースでは、最初から悲しい顔が含まれていません。また、笑顔も含まれていないため、答えは $ 0 $ です。 $ 2 $ つ目のテストケースでは、先頭の悲しい顔 `):` を削除すると、 `):(:` → `(:` となります。最終的な文字列 `(:` には悲しい顔が含まれておらず、笑顔が $ 1 $ つ含まれています。一方、中央の悲しい顔 `:(` を削除し、続けて `):` を削除すると空文字列になり、笑顔の個数は $ 0 $ です。 最終的な笑顔の個数を $ 1 $ より大きくすることはできないため、答えは $ 1 $ です。 $ 3 $ つ目のテストケースでは、例えば以下のように操作できます。 `:)()(():):(::` → `:)()(():(::` → `:)()(((::` 最終的な文字列には悲しい顔が含まれておらず、笑顔が $ 2 $ つ含まれています。これが最大なので、答えは $ 2 $ です。 ### Constraints - $ 1 \le T \le 10^5 $ - $ 1 \le |S| \le 10^6 $ - $ S $ は `:` と `(` と `)` からなる - すべてのテストケースについての $ |S| $ の総和は $ 10^6 $ 以下 - 入力される数値はすべて整数