آقای مهندس سامانه‌ی امنیتی جدیدی برای موزه‌ی جواهرات ملی کار گذاشته است. او برای این کار تعدادی لیزر در مکان‌های متفاوت موزه قرار داده به طوری که اگر دزدی با لیزرها برخورد کند، آژیر خطر به کار می‌افتد. برای امنیت بیشتر، لیزرها ثابت نیستند و بعد از هر دقیقه جهت آن‌ها عوض می‌شود. دقت کنید که لیزرها تنها دو جهت عمودی و افقی دارند. در واقع می‌توان به هر کدام از لیزرها به دید یک نقطه نگاه کرد که در هر زمان راستای افقی یا عمودی را پوشش می‌دهد. (دقت کنید که لیزرها تمامی نقطه‌های یک راستا را پوشش می‌دهند و در واقع پوشش آن‌ها یک خط است و نیم خط نیست)
برای آزمایش سیستم امنیتی آقای مهندس نیاز به برنامه‌ای دارد که موقعیت ابتدایی یک دزد و موقعیت یکی از جواهرهای موزه را بگیرد و کمترین زمانی که طول می‌کشد تا دزد بدون برخورد با لیزرها به جواهر برسد را محاسبه کند. فرض بر این است که در یک دقیقه دزد به تمامی نقاطی که نیازی به عبور از لیزر ندارد می‌تواند برسد. وظیفه‌ی شماست که برنامه‌ی درخواستی آقای مهندس را بنویسید.
خروجی شامل $q$ سطر است که سطر $i$ام پاسخ به پرسش $i$ام آقای مهندس است.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 3 - 3 1 $|$ 1 3 - 5 5 2 2 4 4 2 2 0 0 2 2 6 6 | 0 1 1 |
| 4 3 - 1 1 - 3 3 - 5 5 - 7 7 -1 -1 2 2 2 4 4 2 2 4 4 4 | 1 1 0 |