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.

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\).

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.

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.

提交代码