Dəyirmi Masa Cəngavərləri
İl 573-cü ildir. Kral Artur bütün Britaniyanı idarə edir. O, xalq tərəfindən sevilən ədalətli bir hökmdardır. Lakin belə böyük bir ölkəni idarə etmək çətin bir vəzifədir və bunu etmək çox səy tələb edir. Xoşbəxtlikdən, bu işdə ona ən nəcib Dəyirmi Masa Cəngavərləri kömək edir. Əvvəlcə, bu qurum yalnız krallığın ən cəsur qəhrəmanlarından, məsələn, Sir Qavayn, Sir Lancelot və ya Sir Qalahad kimi şəxslərdən ibarət idi. Lakin son zamanlarda Kral Artur bu müqəddəs dairəyə əlavə üzvlərin qəbul edilməsinin siyasi bir zərurət olduğunu gördü. Bunun əsas səbəbi onun hakimiyyəti altında davam edən sülh dövründə gildiyaların ölkənin idarə olunmasında daha çox təsir tələb etməsidir. "Axı, sülh dövründə qılıncdan çox çörəyə ehtiyacınız var, elə deyilmi?", deyə çörəkçilər gildiyasının rəhbəri söylədi. Müstəsna ədalətli və nəcib bir hökmdar olan Artur razılaşdı.
Bu, Dəyirmi Masa "cəngavərlərinin" sıralarının müəyyən bir şəkildə artmasına səbəb oldu. Artur, dülgərlər gildiyasından daha böyük bir masa sifariş etməli olduğunu gördü (onlar da dərhal masada bəzi yerlər tələb etdilər) və nəticədə onu yerləşdirmək üçün Camelot Qalasına yeni bir qanad əlavə etməli oldu (sonra daş ustalarının nə tələb etdiyini təxmin edə bilərsiniz).
Nəticədə, Dəyirmi Masanın həftəlik iclasları indi olduqca sıx olur. Əslində, o qədər çox insan var ki, masanın əks tərəflərində oturarkən bir-birini başa düşmək çətin ola bilər. Problemin nə qədər böyük olduğunu öyrənmək üçün Artur sizdən Dəyirmi Masanın ətrafında oturan ən uzaq iki üzvün bir-birindən nə qədər uzaqda oturduğunu hesablamağınızı istəyir. İşlər, masada oturan insanların yalnız məhdud sayda olması və onların masanın ətrafında bərabər paylanmaması ilə daha da mürəkkəbləşir — bəziləri vacib məsələləri müzakirə etmək üçün bir-birinə yaxın oturur, digərləri isə qonşularından uzaq durmağa üstünlük verir (məsələn, sağlıqçılar gildiyasının nümayəndəsi və qatil gildiyasının rəhbəri).
Sizin vəzifəniz, masanın ətrafında hər hansı bir cüt stul arasında maksimum məsafəni hesablayan bir proqram yazmaqdır. Bunun üçün sizə masanın ətrafında stulların yerləşdirilməsini göstərən bucaqların (əks istiqamətdə sıralanmış) siyahısı verilir. Masanın radiusu, ətrafında oturan cəngavərlərin sayına bərabərdir.
Giriş verilənləri
Birinci sətir ssenarilərin sayını ehtiva edir. Hər bir ssenari, stulların sayı n olan bir sətirlə başlayır (3 ≤ n ≤ 10000). Bundan sonra n sətir gəlir, hər biri iki tam ədəd p və q (0 ≤ p < q < 10^9) ehtiva edir, bucağı 2p/q göstərir.
Çıxış verilənləri
Hər bir ssenari üçün çıxış "Ssenari #i:" sətiri ilə başlayır, burada i ssenarinin nömrəsidir və 1-dən başlayır. Sonra maksimal məsafəni iki onluq rəqəmlə yuvarlaqlaşdıraraq çap edin. Ssenari üçün çıxışı boş bir sətirlə tamamlayın.