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