Легіон#3934
Легіон — основна організаційна одиниця в армії Стародавнього Риму. У різні періоди легіони мали різну чисельність і шикування. Найпростішим шикуванням була шеренга. Щоб із солдатів легіону, вишикуваних у шеренгу, відібрати трьох у розвідку, виконувалися такі дії: якщо солдатів у шеренці більше трьох, то шеренга розбивалася на дві частини. Одна частина складалася з солдатів, що стоять на парних позиціях, а інша — з тих, що стоять на непарних позиціях. Ця процедура повторювалася для всіх отриманих шеренг доти, поки в кожній з них не залишиться не більше трьох солдатів. Якщо солдатів залишилося троє, то цю групу можна відправити в розвідку.
Необхідно визначити, скільки груп по три особи може бути сформовано з початкової шеренги.
Перший рядок вхідного файлу містить одне число — кількість тестів (T \leq 10^4). Кожен з наступних рядків містить єдине ціле число — кількість солдатів у шеренці (0 \leq N \leq 10^{18}).
Для кожного тесту в окремому рядку виводиться одне ціле число — кількість груп по три особи, сформованих з початкової шеренги.
Приклад 1