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