Grundy`s game
Туга, самотність, біль, дихання ночі –Це, звичайно, зовсім не те, що ти хочешFlёur
Вася любить гру Гранді. Але ніхто не любить Васю. Так щто йому ні з ким грати у цю гру і йому не важливо, хто переможе. Єдине, що цікавить Васю у житті, це чому дорівнює число Гранді для різних купок гри Гранді. І усе, чим він займається днями та ночами, це обчислює ці числа. Ви будете просто безсердечною людиною, якщо не допоможете Васі завершити його обчислення якомога скоріше і відправитись на пошуки роботи, дівчини чи змісту життя.
Нагадаємо правила гри Гранді. Спочатку є одна купка камінців. На кожному ході гравець обирає якусь існуючу купку і ділить її на дві непорожні купки камінців таким чином, щоб вони не були рівні. Програє той, хто не зможе зробити хід.
Вхідні дані
У першому рядку знаходиться число N (1 ≤ N ≤ 10^4) – кількість запитів. Далі йде N рядків, які містять по 1 числу, – розміру чергової купки b_i (1 ≤ b_i ≤ 10^4).
Вихідні дані
Виведіть відповідь на кожен запит – число Гранді чергової купки – у новому рядку.