POLSKI SPOJ

Podzielność przez 4

Dla ilu całkowitych wartości k (0 ≤ k ≤ n), liczba $\left(\begin{array}{c}n\\ k\end{array}\right)$ (n nad k) jest podzielna przez 4?

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 1000). Dla każdego przypadku testowego w osobnym wierszu podana jest jedna liczba naturalna n, (1 ≤ n ≤ 10⁹)

Wyjście
Dla każdego przypadku testowego należy wypisać jedną liczbę będącą odpowiedzią na pytanie postawione w zadaniu.

Przykład

Wejście
2
6
10

Wyjście
1
3

Zadanie posiada 10 testów, każdy test za 10 punktów.
Test 1: (n < 64)
Test ≤ 5: (n < 10⁵)
Test > 5: (10⁵ ≤ n ≤ 10⁹)
Zadanie zostanie zaakceptowane, jeśli uzyskasz co najmniej 50/100 punktów.