eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Grundy`s game

Grundy`s game

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Туга, самотність, біль, дихання ночі –Це, звичайно, зовсім не те, що ти хочешFlёur

Вася любить гру Гранді. Але ніхто не любить Васю. Так щто йому ні з ким грати у цю гру і йому не важливо, хто переможе. Єдине, що цікавить Васю у житті, це чому дорівнює число Гранді для різних купок гри Гранді. І усе, чим він займається днями та ночами, це обчислює ці числа. Ви будете просто безсердечною людиною, якщо не допоможете Васі завершити його обчислення якомога скоріше і відправитись на пошуки роботи, дівчини чи змісту життя.

Нагадаємо правила гри Гранді. Спочатку є одна купка камінців. На кожному ході гравець обирає якусь існуючу купку і ділить її на дві непорожні купки камінців таким чином, щоб вони не були рівні. Програє той, хто не зможе зробити хід.

Вхідні дані

У першому рядку знаходиться число N (1N10^4) – кількість запитів. Далі йде N рядків, які містять по 1 числу, – розміру чергової купки b_i (1b_i10^4).

Вихідні дані

Виведіть відповідь на кожен запит – число Гранді чергової купки – у новому рядку.

Приклад

Вхідні дані #1
4
1
2
3
4
Вихідні дані #1
0
0
1
0
Автор Олег Петров
Джерело Летняя школа Севастополь 2013, Волна 1, День 3