Baş Mağaralar#6105
Beynəlxalq bir ekspedisiya səhranın ortasında yerləşən nəhəng bir uçurumda tərk edilmiş Buddist mağara məbədlərini kəşf etdi. Uçurumun ortasında qazılmış bir çox kiçik mağara var idi və onlar kvadrat şəbəkələrdə düzülmüşdü. Ekspedisiya arxeoloqları bu mağaralardakı Budda heykəllərindən çox təsirləndilər. Daha da maraqlı olan, bəzi mağaralarda gizlədilmiş Buddizm sutralarının (müqəddəs kitablar) rulonları idi. Bu rulonların min ildən çox əvvəl yazıldığı və ölçülməz dəyərə malik olduğu düşünülür.
Ekspedisiya rəhbəri mümkün qədər çox rulon toplamaq istəyirdi. Lakin mağaralara daxil olmaq asan deyildi, çünki onlar uçurumun ortasında yerləşirdi. Mağaraya daxil olmağın yeganə yolu helikopterdən asılmaq idi. Mağaraya daxil olub onu araşdırdıqdan sonra, mağaranızın altındakı üç mağaradan birinə enə bilərsiniz; yəni, ya mağaranızın birbaşa altında olan mağara, ya da birbaşa altındakı mağaranın solunda və ya sağında olan mağaralar. Bunu istədiyiniz qədər təkrarlaya bilərsiniz və sonra uzun bir ip vasitəsilə yerə enə bilərsiniz.
Beləliklə, bir cəhddə bir neçə mağaranı araşdıra bilərsiniz. Amma hansı mağaraları ziyarət etməlisiniz? İlkin cəhdlərin nəticələrini araşdıraraq, ekspedisiyanın riyaziyyatçı üzvü aşkar etdi ki, (1) mağaralar mərkəzi birindən başlayaraq, Şəkil 1-də göstərildiyi kimi spiral şəklində nömrələnə bilər; və (2) yalnız mağara nömrələri sadə olan mağaralar (belə mağaraları sadə mağaralar adlandıraq), şəkildə dairəvi olanlar, rulonlar saxlayır. Növbəti cəhddən etibarən, araşdırmaq üçün sadə mağaraların sayını maksimuma çatdıra bilərsiniz.
Şəkil 1: Mağaraların nömrələnməsi və sadə mağaralar
Bir proqram yazın ki, mağaraların ümumi sayı və ilk ziyarət edilən mağara verildikdə, maksimum sayda sadə mağara ehtiva edən enmə marşrutunu tapsın.
Giriş bir neçə datasetdən ibarətdir. Hər bir dataset bir sətirdə boşluqla ayrılmış bir tam ədəd m (1 ≤ m ≤ 10^6) və bir tam ədəd n (1 ≤ n ≤ m) ehtiva edir. m mağaraların ümumi sayını təmsil edir. n isə araşdırmaya başlayacağınız mağaranın nömrəsini təmsil edir. Son datasetdən sonra iki sıfır olan bir sətir gəlir.
Hər bir dataset üçün mağara n-dən başlayan və ən çox sadə mağara ehtiva edən yolu tapın və bir sətirdə həmin yoldakı sadə mağaraların sayını və yoldakı son sadə mağaranın nömrəsini boşluqla ayrılmış şəkildə çıxarın. İlk araşdırılan mağara n də yoldakı mağaralara daxildir. Əgər belə bir neçə yol varsa, son sadə mağaranın nömrəsi ən böyük olan yolu çıxarın. Sadə mağaraları araşdıran belə bir yol olmadıqda, "0 0" (tırnaq işarələri olmadan) çıxarın.
Nümunə 1