Розділи купку

Двоє гравців беруть участь у грі "Розділи купку". Спочатку є купка з n цукерок. Будь-яку з купок можна розділити на дві купки різного розміру. Гравець, який не може зробити хід, програє. Скільки існує способів для першого гравця зробити перший хід так, щоб при оптимальній грі обох гравців він виграв.

Вхідні дані

Перший рядок містить кількість партій t (1 ≤ t ≤ 10^4). У наступних t рядках наведено опис кожної партії: n (1 ≤ n ≤ 10^4).

Вихідні дані

Для кожної партії виведіть кількість способів, за допомогою яких перший гравець може зробити перший хід, щоб виграти при оптимальній грі обох. Якщо перший гравець не може виграти, виведіть 0.

Приклади