Є лише одна купка з деякою кількістю камінчиків. За один хід дозволяється взяти з купки довільну кількість камінчиків, але таку, яка дозволена правилами. Хто не зміг зробити хід - той програв.
Пограйте у цю гру і напишіть програму, яка дасть відповідь, хто ж при заданій кількості камінчиків та правилах виграє при оптимальній стратегії: той хто ходить першим, чи другим.
Вхідні дані містять декілька рядків, кількість яких T не перевищує 10. У кожному рядку задано спочатку кількість камінчиків у купці M (1 <= M <= 10^6), потім кількість правил (дозволених ходів) N (1 <= N <= 10), а далі до кінця рядка N чисел, що описують самі правила.
Єдиний рядок, що складається з T символів 1 або 2 - номерів гравців, які виграють, для кожного тестового випадку.