Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 4021
Boolean Expression

Time Limit: 1 Second      Memory Limit: 65536 KB

Given a valid boolean expression consisting of seven types of characters 'T' (true), 'F' (false), '!' (not), '&' (and), '|' (or), '(' (left bracket) and ')' (right bracket), you can add any number of these seven types of characters into the expression to make it true (of course, the expression must still be valid).

Please calculate the minimum number of characters you have to add into the expression to make it true.

The priority of the boolean operators are: '!' > '&' > '|', just the same as their priority in most of the programming languages.

To be specific, a valid boolean expression can be expressed by the following BNF,

<bool> ::= 'T' | 'F' | '(' <expr> ')'
<not-expr> ::= '!' <not-expr> | <bool>
<and-expr> ::= <and-expr> '&' <not-expr> | <not-expr>
<expr> ::= <expr> '|' <and-expr> | <and-expr>

where <expr> is a valid boolean expression.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and only line contains a boolean expression $s$ ($1 \le |s| \le 5 \times 10^5$) without space consisting of 'T', 'F', '!', '&', '|', '(' and ')'.

It's guaranteed that the given expression is valid, and the sum of $|s|$ over all test cases will not exceed $5 \times 10^6$.

Output

For each test case output one line containing one integer, indicating the minimum number of characters you have to add into the expression to make it true.

Sample Input

4
!T&F
T&!F|T&F
(T&(!T|(!!F))&T)
!!!!!F


Sample Output

2
0
1
0


Hint

For the first sample test case, we can add a pair of brackets and change the expression to !(T&F).

For the second sample test case, note that the priority of '&' is higher than '|', so the original expression is already true.

For the third sample test case, we can add a '!' and change the expression to !(T&(!T|(!!F))&T).

We kindly remind you that the stack size of the online judge system is limited to 8M, so please use your stack space wisely.

Author: WENG, Caizhi
Source: The 18th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status