Cho một mảng \(s\) gồm \(2 \times n\) ký tự, trong đó có \(n\) ký tự '[' và \(n\) ký tự ']'. Xâu \(s\) được gọi là viết đúng nếu \(s\) có dạng \(s_2[s_1]\) trong đó \(s_1\), \(s_2\) là các xâu viết đúng. Nhiệm vụ của bạn là tìm số các phép đổi chỗ ít nhất các ký tự kề nhau của xâu \(s\) viết sai để \(s\) trở thành viết đúng. Ví dụ với xâu \(s = "[]][]["\) ta có số phép đổi chỗ kề nhau ít nhất là \(2\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(t\) (\(1 \le t \le 100\)).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một xâu \(s\) (\(1 \le |s| \le 10^5\)) viết sai theo nguyên tắc kể trên.

Output

• Một dòng duy nhất in ra kết quả.

Example

2
[]][][
[][][]

2
0