PIPI有一个括号序列(不一定是合法括号序列)，现在它想请你计算出这个括号序列中有多少个非空子段是合法括号序列？

合法括号序列的定义是：

1.空序列是合法括号序列。

2.如果S是合法括号序列，那么(S)是合法括号序列。

3.如果A和B都是合法括号序列，那么AB是合法括号序列。

多组测试用例。
接下来T行，每行一个由'('和')'组成的非空串S，|S|<=1000000.
保证所有的|S|之和不超过1000000.

输出给定括号序列中合法非空子段的个数。

中等