Есть \textbf{N} кучек с камешками. За один ход разрешается либо забрать любое количество камешков из одной кучки, либо разделить кучку на две более мелкие. Побеждает тот, кто забирает последний камешек. Нужно определить, кто победит при оптимальной стратегии: тот кто делает ход первым или вторым. \InputFile В первой строке задано количество тестовых случаев \textbf{T} (\textbf{1} <= \textbf{T} <= \textbf{100}) Далее следует \textbf{T} пар строк, в первой из которых находится значение \textbf{N}, а во второй через пробел количества камушков в каждой из кучек \textbf{S_i}. \textbf{1} <= \textbf{N} <= \textbf{10^3} \textbf{1} <= \textbf{S_i} <= \textbf{10^6} \OutputFile Единственная строка, состоящая из последовательности \textbf{1} и \textbf{2} - номера победивших игрока.