Лише одна купка?

Є лише одна купка з деякою кількістю камінчиків. За один хід дозволяється взяти з купки довільну кількість камінчиків, але таку, яка дозволена правилами. Хто не зміг зробити хід - той програв.

Пограйте у цю гру і напишіть програму, яка дасть відповідь, хто ж при заданій кількості камінчиків та правилах виграє при оптимальній стратегії: той хто ходить першим, чи другим.

Вхідні дані

Вхідні дані містять декілька рядків, кількість яких T не перевищує 10. У кожному рядку задано спочатку кількість камінчиків у купці M (1 <= M <= $10^6$), потім кількість правил (дозволених ходів) N (1 <= N <= 10), а далі до кінця рядка N чисел, що описують самі правила.

Вихідні дані

Єдиний рядок, що складається з T символів 1 або 2 - номерів гравців, які виграють, для кожного тестового випадку.

Приклади