Strategiya oyunu#1297
— Tülkü, nə üçün bu qədər çox qızılgül ləçəkləri toplamısan?
— Onlarla, Balaca şahzadə, biz səni irəliyə düşünməyə öyrədəcək oyun oynayacağıq. Bu ən vacib müdriklərdindən biridir: yalnız indini deyil, gələcəyi də görə bilmək.
— Necə oynayırıq?
— Qaydalar sadədir, lakin onları başa düşmək əsl müdriklik tələb edir: mən ləçək yığını düzəldəcəyəm. Sonra növbə ilə onları götürəcəyik və sən birinci gedəcəksən. Hər gedişdə oyunçu ən azı bir və ən çoxu yığınından istədiyi qədər ləçək götürə bilər. Son ləçəyi götürən qalib olur. Amma unutma: vacib olan yalnız indi gördüyün deyil, gedişindən sonra baş verəcək hadisələrdir.
— Bu həqiqətən irəliyə düşünməyi tələb edir...
— Məhz belədir. Əsl strategiya — hələ baş verməmiş hadisələri görə bilmək bacarığıdır.
Sənin tapşırığın: hər oyunun qalibini müəyyən et, əgər hər iki oyunçu — həm Balaca şahzadə, həm də Tülkü — mümkün olan ən yaxşı şəkildə oynayarsa.
Birinci sətirdə oyunların sayı olan müsbət tam ədədi verilir (1 \leq T \leq 100). Sonrakı oyun mövqeyinin başlanğıc vəziyyətini təsvir edən cüt sətirdən ibarətdir: birinci sətirdə (1 \leq N \leq 10000) və müsbət tam ədədləri, ikinci sətirdə isə ədəd S_i (0 \leq S_i \leq 2147483647) verilir; burada S_i hər yığındakı ləçəklərin sayıdır.
Hər test üçün ayrıca sətirdə "Masha wins" əgər Balaca şahzadə qalib gəlirsə (o birinci gedir), yaxud "Misha wins" əgər Tülkü qalib gəlirsə yazın.
Nümunə 1