Yalnız bir dəstə?

Yalnız bir yığın çınqıl var. Bir gedişdə yığından istənilən sayda çınqıl götürmək olar, lakin bu, qaydalarla icazə verilən qədər olmalıdır. Gediş edə bilməyən uduzur.

Bu oyunu oynayın və verilmiş çınqıl sayı və qaydalarla optimal strategiya ilə kimin qalib gələcəyini müəyyən edən bir proqram yazın: birinci gedən, yoxsa ikinci.

Giriş verilənləri

Giriş məlumatları T sayını keçməyən bir neçə sətirdən ibarətdir, burada T maksimum 10 ola bilər. Hər sətirdə əvvəlcə yığındakı çınqıl sayı M (1 <= M <= $10^6$), sonra qaydaların (icazə verilən gedişlərin) sayı N (1 <= N <= 10), və daha sonra sətirin sonuna qədər N qaydanı təsvir edən rəqəmlər verilir.

Çıxış verilənləri

Hər test halı üçün qalib gələn oyunçuların nömrələrindən ibarət T simvoldan ibarət yeganə sətir, 1 və ya 2.

Nümunələr