Vasya Delinyaya qarşı
Və artıq siz "Arnoldun Bit Düzülüşü" məsələsindən bildiyiniz kimi, məktəbli Vasya çox maraqlıdır və daim İnternetdə yeni bir şey axtarır. Tamamilə yaxınlarda Vasyanın çox bəxti gətirdi - o, Arnoldun video mühazirəsini tapdı və həmin axşam diqqətlə izlədi. Ertəsi gün məktəbdə proqramlaşdırma üzrə fakültativdə o, sizə həll etməyi təklif etdiyi aşağıdakı məsələni düşündü.
Verilmiş bəzi qeyri-mənfi tam ədəd - bu, Arnoldun ardıcıllığının ilk üzvüdür. İndi bu ədədi ikilik say sistemində təqdim etmək və alınan bit təqdimatı üzərində aşağıdakı əməliyyatları yerinə yetirmək lazımdır: ardıcıllığın növbəti ədədində yeni bitin dəyəri bu və növbəti bitin cəminə 2 moduluna bərabər olacaq. Son bitin sağında qonşusu olmadığı üçün Vasya əməliyyatı yerinə yetirmək üçün həmin Arnoldun tövsiyəsi ilə sonunda yenidən ilk biti əlavə edirdi. Vasya təəccüblə gördü ki, müəyyən bir addımda bu şəkildə alınan ardıcıllıq periodik olur - görünür, Arnold da bu barədə nəsə danışmışdı, amma Vasya artıq bunu dəqiq xatırlamır...
Və Vasya Arnoldun mühazirəsindən bu sözləri də xatırladı: "görkəmli amerikalı riyaziyyatçı, Filds mükafatı laureatı Deligne bir dəfə Moskvaya gəldi və biz onunla mənim digər nəticələrimi müzakirə etdik və o mənə dedi: "Bu necə teoremdir ki, sən cəmi qırx milyon nümunə nəzərdən keçirmisən"…". Buna görə Vasya, birincisi, tədqiqatlarının diapazonunu genişləndirmək və ikincisi, "Yuxarıda təsvir olunan alqoritmin hansı addımında belə bir periodik ardıcıllığın ilk üzvü əldə ediləcək və bu ardıcıllığın periodunun uzunluğu nədir?" tipli çoxsaylı sorğulara tez cavab verməyi öyrənmək qərarına gəldi.
Vasyaya belə sorğulara tez cavab tapmaqda kömək edin.
Giriş verilənləri
Giriş faylının hər bir sətirində n vahid qeyri-mənfi tam ədəd yerləşir ki, bu da 10^10-u keçmir - ardıcıllığın ilk üzvü.
Çıxış verilənləri
Girişdə alınan hər bir sorğu üçün ayrıca sətirdə axtarılan iki ədədi boşluqla ayıraraq çıxarın: belə bir periodik ardıcıllığın ilk periodik üzvünün əldə edilməsi addımı və bu ardıcıllığın periodunun uzunluğu.