問題文

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 個のテストケースについて答えてください。

制約

• 1 \le T \le 10^5
• 1 \le |S| \le 10^6
• S は : と ( と ) からなる
• すべてのテストケースについての |S| の総和は 10^6 以下
• 入力される数値はすべて整数

入力例 1

3
:
):(:
:)()(():):(::

出力例 1

0
1
2

1 つ目のテストケースでは、最初から悲しい顔が含まれていません。また、笑顔も含まれていないため、答えは 0 です。

2 つ目のテストケースでは、先頭の悲しい顔 ): を削除すると、

):(: → (:

となります。最終的な文字列 (: には悲しい顔が含まれておらず、笑顔が 1 つ含まれています。一方、中央の悲しい顔 :( を削除し、続けて ): を削除すると空文字列になり、笑顔の個数は 0 です。

最終的な笑顔の個数を 1 より大きくすることはできないため、答えは 1 です。

3 つ目のテストケースでは、例えば以下のように操作できます。

:)()(():):(:: → :)()(():(:: → :)()(((::

最終的な文字列には悲しい顔が含まれておらず、笑顔が 2 つ含まれています。これが最大なので、答えは 2 です。