Кісточки для Шарика 2
Малюнок Шишко Марини - 12.05.2010, 9 кл.
Нарешті Пєчкін почав приносити для Шарика обіцяни кісточки... Так як кісточок було багато, і наближалась зима, Шарик почав складати їх по кучкам, причому у кожній кучці не більше 100 кісточок, а всього кучок не більше, ніж 10000.
"Замяучили мене ці суперечки з приводу двійкової чи трійкової логіки" - подумав Матроскін, - "адже все-рівно трійкову можна звести до двійкової", вирішив розумний кіт і тут же придумав нову гру. Він пронумерував всі кучки підряд і запропонував Шарику не просто сидіти і чекати чергового приходу Пєчкіна, а пограти з ним у таку гру. Ходять по черзі, але Матроскін завжди першим. Гравець, який робить хід, спочатку вибирає кучку з кількістю кісточок A, а потім B, дотримуючись наступних вимог:
Кучка A повинна бути не порожнью.
Кучка B повинна бути строго менша за A.
Кучка B також повинна бути не порожньою.
Обов'язково повинні виконуватись умови, що сумарна кількість A + B не ділиться націло на 2 і ділиться націло на 3 (до питання про двійкову і трійкову логіку... :) ).
З кучки B взяти довільну, але більшу нуля кількість кісточок.
Хто не зміг зробити хід - той програв.
Хто виграє у цій грі при оптимальній стратегії обох гравців?
Вхідні дані
У першому рядку задано кількість ігор між Матроскіним та Шариком за день T (1 ≤ T ≤ 100). Далі йде T рядків, у кожному з яких спочатку задано кількусть кучок N, а потім N чисел, які визначають кількість кісточок у відповідній кучці.
Вихідні дані
Вивести один рядок, який складається з послідовності T одиниць або двійок: 1 - якщо виграв Матроскін, 2 - Шарик.