در بازی «جواهر سلطنتی»، به شما یک جدول $n \times m$ و تعداد زیادی سنگ‌های قیمتی از نوع یاقوت، زمرد، فیروزه و الماس داده شده است. شما باید در هر خانه‌ی جدول یک سنگ قیمتی بگذارید بطوری‌که شرایط زیر برقرار باشد:

1. هر یاقوت دست‌کم یک زمرد، یک فیروزه و یک الماس در همسایگی‌اش دارد.
2. هر زمرد دست‌کم یک فیروزه و یک الماس در همسایگی‌اش دارد.
3. هر فیروزه دست‌کم یک الماس در همسایگی‌اش دارد.

همسایه‌ی یک خانه در جدول، یکی از ۴ خانه‌ای‌ است که دقیقاً بالا، چپ، راست یا پایین آن خانه باشد. برنامه‌ای بنویسید که بیش‌ترین تعداد یاقوت را بیابد که می‌توان با حفظ شرایط بالا در جدول قرار داد.

• هر فایل ورودی شامل تعدادی تست است. هر تست شامل ۲ عدد $n$ ($1 \le n \le 8$) و $m$ ($1 \le m \le 8$) است.
• فایل ورودی با خط $0 \ 0$ پایان می‌یابد.

برای هر تست، یک خط خروجی دهید شامل یک عدد نشان‌دهنده‌ی بیش‌ترین تعداد یاقوت که در جدول می‌توان قرار داد.

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

• سوال قبل