Bölmək ya götürmək?

Əlinizdə N sayda daş yığını var. Bir gedişdə ya bir yığından istənilən sayda daş götürə bilərsiniz, ya da yığını iki kiçik yığına bölə bilərsiniz. Sonuncu daşı götürən oyunçu qalib olur.

Hər iki oyunçu ən yaxşı strategiyanı tətbiq etdikdə, oyunu ilk başlayan oyunçu, yoxsa ikinci başlayan oyunçu qazanacaq? Bunu müəyyənləşdirmək lazımdır.

Giriş verilənləri

Birinci sətirdə test halların sayı T (1 <= T <= 100) verilir. Sonra T test üçün məlumat verilir. Hər bir testdə birinci sətirdə N dəyəri, ikinci sətirdə isə hər bir yığındakı daşların sayı S_i boşluqla ayrılmış şəkildə verilir.

1 <= N <= 10^3

1 <= S_i <= 10^6

Çıxış verilənləri

Hər bir test üçün qalib gələcək oyunçunun nömrəsini (1 və ya 2) ehtiva edən tək bir sətir çıxarın.

Nümunələr