Mumiya Dəliliyi
Ekskursiya zamanı 2011 ACM-ICPC Dünya Finalında səhrada köhnə bir Misir məzarına rast gəlirsiniz. Təəssüf ki, məzarı açmaq pis bir fikir olur: bir neçə dəqiqə əvvəl boş olan səhrada indi əsəbi mumiyalarla dolu bir səhraya çevrilir (əgər bir neçə min illik sakit yuxudan qəflətən oyansaydınız, siz də əsəbi olardınız). (Xoşbəxtlikdən, bu problemi həll etdikdən sonra Florida'da bir otel otağında sağ-salamat oyandınız. Qəzəbli mumiyalar sadəcə bir yuxu idi.)
Bu qatil mumiyalar kütləsi ilə üzləşdiyinizdə, yeganə şansınız qaçmaq və onlar sizi tutmadan qaçmağa çalışmaqdır. Sual budur: bir mumiya sizi tutana qədər nə qədər vaxt keçəcək, əgər nə siz, nə də mumiyalar heç vaxt yorulmazsa?
Səhranı kvadratlarla dolu bir şəbəkə kimi modelləşdiririk. Siz və mumiyalar növbə ilə şəbəkədə hərəkət edirsiniz. İlk hərəkəti siz edirsiniz. Öz növbənizdə, cari yerinizə bitişik olan səkkiz kvadratın hər hansı birinə hərəkət edə bilərsiniz və ya yerinizdə qala bilərsiniz. Mumiyaların növbəsində, hər bir mumiya sadəcə ona ən yaxın olan bitişik kvadrata hərəkət edir (Öklid məsafəsi ilə ölçülür, siz və bütün mumiyalar öz müvafiq kvadratlarının mərkəzində durduğunuzu fərz edirik. Yoxsa fərz etmirdik?). İki mumiya eyni kvadratda ola bilər.
Bir zaman addımı sizin hərəkətinizdən və mumiyaların hərəkətlərindən ibarətdir. Bir mumiya sizi tutarsa, o sizin olduğunuz kvadrata hərəkət edir və ya siz mumiyanın olduğu kvadrata hərəkət edirsiniz. Əlbəttə ki, mümkün qədər uzun müddət tutulmamağa çalışırsınız. Neçə zaman addımından sonra tutulacaqsınız?
Şəkil I.1: Mumiya təqibi
Şəkil, dörd mumiya tərəfindən təqib edildiyinizdə nə baş verə biləcəyini göstərir. H ilə işarələnmiş kvadrat sizin başlanğıc mövqeyinizdir və M ilə işarələnmiş kvadratlar mumiyaların başlanğıc mövqeləridir. Dörd zaman addımından sonra, başlanğıc mövqeyinizə görə (3, 4) mövqeyində olan mumiya tərəfindən tutulursunuz.
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Hər test halı səhrada olan mumiyaların sayını verən bir tam ədəd n (0 ≤ n ≤ 10^5) ilə başlayır. Növbəti n sətir hər biri səhranın koordinatlarında (x, y) mövqeyində bir mumiyanın olduğunu göstərən iki tam ədəd x və y ehtiva edir, burada x və y hər ikisi mütləq dəyəri ilə 10^6 ilə məhdudlaşdırılmışdır. Sizin başlanğıc mövqeyiniz (0, 0) və heç bir mumiya bu mövqedə başlamır.
Son test halı -1 ədədini ehtiva edən bir sətirlə tamamlanır.
Çıxış verilənləri
Hər test halı üçün, test halı nömrəsini və tutulana qədər maksimum zaman addımlarının sayını (sizin əldə etdiyiniz ümumi növbə sayısı kimi ölçülür) və ya əgər tutulmadan sonsuzadək qaça bilirsinizsə "heç vaxt" sözünü göstərin.
Nümunə çıxış formatına uyğun olun.