Розділи купку#3712
Двоє гравців беруть участь у грі "Розділи купку". Спочатку є купка з цукерок. Будь-яку з купок можна розділити на дві купки різного розміру. Гравець, який не може зробити хід, програє. Скільки існує способів для першого гравця зробити перший хід так, щоб при оптимальній грі обох гравців він виграв.
Перший рядок містить кількість партій (1 \le t \le 10^4). У наступних рядках наведено опис кожної партії: (1 \le n \le 10^4).
Для кожної партії виведіть кількість способів, за допомогою яких перший гравець може зробити перший хід, щоб виграти при оптимальній грі обох. Якщо перший гравець не може виграти, виведіть 0.
Приклад 1