\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 Виведіть відповідь на кожен запит -- число Гранді чергової купки -- у новому рядку.