آقای کشاورز یک مزرعه‌ی مستطیلی در سرزمین جدید دارد. او مزرعه‌ی خود را به $n×m$ مربع هم اندازه تقسیم کرده است. او در هر مربع به طور کامل یا گندم کاشته‌ است و یا ذرت. آقای کشاورز قاعده‌ی ساده‌ای برای بهبود کیفیت غلات یافته است: اگر $"1"$ نشان‌دهنده‌ی گندم و $"2"$ نشان‌دهنده‌ی ذرت باشد؛ آن‌گاه در مزرعه‌ی او نباید هیچ مجموعه مربع $2×2$ و مجاوری وجود داشته باشد که یکی از الگوهای «تقاطع» زیر را داشته باشد:

آقای کشاورز یک ماشین درو برای برداشت غلات دارد. برای برداشت هر نوع غله، او باید تیغه‌ی خاصی به ماشین درو متصل کند. در ابتدا هیچ تیغه‌ای به به ماشین درو وصل نیست؛ و همچنین، در زمان تعویض تیغه‌ی درو، کشاورز می‌تواند ماشین درو را، بدون این که غله‌ای درو کند، به هر جایی از مزرعه منتقل کند. با این وجود، وقتی که یک تیغه متصل باشد، ماشین درو تنها می‌تواند در مربع‌هایی حرکت کند که یا حاوی غله‌ی متناسب با تیغه هستند، و یا مربع‌هایی که غله‌ای در آن‌ها نیست (آن‌هایی که قبلا درو شده‌اند).

با توجه به دشواری کار تعویض تیغه، کشاورز می‌خواهد شما را استخدام کند تا به او بهترین راه برای درو کردن کل مزرعه را با کمترین تعداد تعویض تیغه نشان بدهید. وظیفه‌ی شما نوشتن برنامه‌ای است که به کشاورز کمک کند این عدد کمینه را بیابد.

ورودی شامل چندین سناریو است. در خط اول هر سناریو دو عدد صحیح $n$ و $m$ آمده است $ (1 \leq n×m \leq 10^5) $ که به ترتیب مشخص کننده‌ی تعداد سطرها و ستون‌های مزرعه هستند. $n$ خط بعدی، هر یک شامل $m$ کاراکتر از مجموعه‌ی $\{1,2\}$ می‌باشند، که مشخص کننده‌ی نوع غله در مربع متناظر با آن در مزرعه است. ورودی با خطی شامل $"0\ 0"$ پایان می‌یابد.

به ازای هر سناریو در یک خط، کمینه‌ی تعداد دفعاتی که کشاورز باید تیغه‌ی ماشین درو را عوض کند چاپ کنید. اولین باری که یک تیغه به ماشین درو متصل می‌شود هم به عنوان یک تعویض تیغه شمرده می‌شود.

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

• سوال بعد
• سوال قبل