• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

«دکارتی» تردستی ماهر است. وقتی دست دکارتی از روی کارتی رد شود، کارت برعکس می‌شود. (یعنی اگر کارت رو باشد پشت می‌شود و اگر پشت باشد رو می‌شود.) آقای دکارتی می‌خواهد $t$ روز متوالی تردستی کند. در هر روز تعدادی کارت پیش روی او است و او در یک عملیات می‌تواند بازه‌ای دلخواه و متوالی از کارت‌ها را برعکس کند. او می‌خواهد حداقل تعداد عملیات که همه کارت‌ها به سمت رو تبدیل شوند را بداند!

ورودی

در خط اول $t$ می‌آید که نشان دهنده تعداد روزهایی است که آقای دکارتی تردستی می‌کند. $$1 \leq t \leq 1000$$

در $t$ خط بعد، در هر کدام یک رشته می‌آید که حرف $i$ام آن اگر 1 باشد یعنی کارت $i$ام رو است و اگر 0 باشد یعنی کارت $i$ام به پشت قرار دارد.

تعداد کارت‌های هر روز حداکثر ۵۰ است.

خروجی

در خط $i$ام از $t$ خط جواب مساله را خروجی دهید.

مثال

ورودی نمونه ۱

5
01
00010
11011
111000
101010101

خروجی نمونه ۱

1
2
1
1
4

• در روز اول بازه‌ی $[1,1]$ را برعکس کند.
• در روز دوم بازه‌های $[4,4]$ و $[1,5]$ را برعکس کند.
• در روز سوم بازه‌ی $[3,3]$ را برعکس کند.
• در روز چهارم بازه‌ی $[4, 6]$ را برعکس کند.
• در روز پنجم بازه‌های $[2, 2]$، $[4, 4]$، $[6 ,6]$ و $[8 ,8]$ را برعکس کند.