Las amígdalas de \(\href{https://algo.danimania.dev/account/11}{\color{blue}{\underline{\text{MindTheGap}}}}\) (MTG) están conspirando para acabar con él. Han decidido cubrir su garganta de placas para que no pueda competir en la próxima competición de la famosa plataforma AlgoMania. Además, se lo han tomado como un juego y han decidido competir entre ellas.
Podemos ver la garganta de MTG como una cuadrícula \(1\) x \(N\), es decir, \(N\) casillas dispuestas horizontalmente en la misma fila.
Jugarán por turnos, y en cada turno escogen una posición de la lista y ponen una placa, de tamaño \(1\) x \(3\), centrada en esa posición. En el caso de colocarla en un extremo, se ignorará la casilla que quedaría fuera de la cuadrícula.
Una vez se pone una placa en una posición \(i\) (\(1 \le i \le n\)), no se podrá repetir esa posición en el resto de la partida, pero sí las adyacentes, es decir, se pueden solapar placas parcialmente solo en los extremos.
Empezará jugando la amígdala izquierda y se irán turnando alternadamente. La primera amígdala que no pueda colocar una placa perderá. Ambas juegan de forma óptima.
Entrada
La primera línea contiene un entero \(t\) (\(1 \le t \le 1000\)), el número de casos de prueba.
Las siguientes \(t\) líneas contienen un entero \(n\) (\(1 \le n \le 3000\)), el tamaño de la cuadrícula con la que jugarán las amígdalas.