\textit{Тоска, одиночество, боль, дыхание ночи --Это, конечно, совсем не то, что ты хочешь}Flёur Вася любит игру Гранди. Но никто не любит Васю. Так что ему не с кем играть в эту игру и ему не важно, кто победит. Единственное, что интересует Васю в жизни, это чему равно число Гранди для разных кучек игры Гранди. И всё, чем он занимается днями и ночами, это вычисляет эти числа. Вы будете просто бессердечным человеком, если не поможете Васе завершить его вычисления как можно скорее и отправиться на поиски работы, девушки или смысла жизни. Напомним правила игры Гранди. Вначале есть одна кучка камней. На каждом ходу игрок выбирает какую-то существующую кучку и разделяет её на две непустые кучки камней таким образом, чтобы они не были равны. Проигрывает тот, кто не может сделать ход. \InputFile В первой строке находится число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^4}) -- количество запросов. Далее следуют \textbf{N} строк, содержащие по \textbf{1 }числу, -- размеру очередной кучки \textbf{b_i} (\textbf{1} ≤ \textbf{b_i} ≤ \textbf{10^4}). \OutputFile Выведите ответ на каждый запрос -- число Гранди очередной кучки -- в новой строке.