Let \(S\) be a set of strings. \(S∗\)
is a set of the empty string and any concatenation of strings in \(S\) (each string in \(S\) can appear multiple times).

Given \(n\) strings \(T_1, ..., T_n\). For each \(T_i\), find the least number of characters to remove to satisfy \(T_i \in \{0, 01, 10\}\)

Input

• The first line of input contains one integer \(n (1 \le n \le 10^6)\).

• The following \(n\) lines, each contains a string \(T_i\). The total length of all \(T_i\) will not exceed \(10^6\)

Output

• Output \(n\) lines, one integer on each line show the number of characters to remove for the respective input.

Example

2
00110
110

0
1