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

---

«دکارتی» تردستی ماهر است. وقتی دست دکارتی از روی کارتی رد شود، کارت برعکس می‌شود. (یعنی اگر کارت رو باشد پشت می‌شود و اگر پشت باشد رو می‌شود.) آقای دکارتی می‌خواهد \(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]\) را برعکس کند.