Is Convertible Data

For each string, you may take at most one parenthesis out of its position and insert it at any position; determine whether the string can become an ordinary valid parenthesis string. Not moving anything is allowed. Output 1 or 0.

输入格式

The first line contains n, followed by n lines of parenthesis strings. 1≤n≤200000, each string has length 1..200000, the total length is ≤200000, and only left and right parentheses appear.

输出格式

Output n values, each 0 or 1, in the same order as the input strings.

样例 1

输入：

3
)(
()
))((

输出：

1 1 0

样例 2

输入：

2
(()
())

输出：

0 0

样例 3

输入：

2
())(
()()

输出：

1 1

样例说明

The examples give 1 1 0; 0 0; and 1 1 respectively.