В ожидании новых приключений Башмачок захотел совершить доброе дело. Посовещавшись с Картой и Рюкзаком, он решил подарить Даше связный граф. После долгих поисков, Башмачок выбрал $$$t$$$ вариантов графа, которые могли бы понравиться Даше, но, к сожалению, все его планы решил испортить лис Жулик.

Жулик знает, что Даша пока умеет считать только до $$$3$$$, поэтому у него родилась идея. Он хочет украсть непустой набор вершин так, чтобы Даша не заметила пропажи. Поэтому он решил украсть непустой набор вершин такой, что если удалить выбранные вершины и связанные с ними рёбра из графа, то для любой из оставшихся вершин будет верно, что её степень (число смежных рёбер) будет иметь такой же остаток от деления на $$$3$$$, что и степень до удаления рёбер. Также он понял, что будет слишком подозрительно, если он украдёт все вершины, поэтому он решил воздержаться от такой соблазнительной затеи.

Башмачок понял, что он не может позволить случиться преступлению. Но он боится, что одному ему не справиться. Поэтому он решил попросить у вас помощи. Башмачок хочет для каждого варианта графа узнать, сможет ли Жулик осуществить свои злобные планы, или нет.