{"code":"icpc21binstrset","name":"Binary String Set","description":"Let $S$ be a set of strings. $S∗$\r\nis a set of the empty string and any concatenation of strings in $S$ (each string in $S$ can appear multiple times).\r\n\r\nGiven $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\\}$\r\n\r\n

Input

\r\n\r\n- The first line of input contains one integer $n (1 \\le n \\le 10^6)$.\r\n\r\n- The following $n$ lines, each contains a string $T_i$. The total length of all $T_i$ will not exceed $10^6$\r\n\r\n

Output

\r\n\r\n- Output $n$ lines, one integer on each line show the number of characters to remove for the respective input.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 2\r\n 00110\r\n 110\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 0\r\n 1\r\n ```","points":400.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}