POLSKI SPOJ

Masz do dyspozycji n-wierzchołków. Na ile sposobów możesz z nich zbudować rozłączne trójkąty i czworokąty tak, aby wszystkie wierzchołki zostały wykorzystane?

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę przypadków testowych. Każdy przypadek testowy to jedna liczba całkowita n (1 ≤ n ≤ 10⁹) oznaczająca liczbę wierzchołków.

Wyjście

Na wyjściu, w osobnym wierszu dla każdego przypadku testowego, należy wypisać jedną liczbę będącą odpowiedzią na pytanie postawione w treści zadania.

Przykład

Dla danych wejściowych:

5
3
4
5
12
15

poprawną odpowiedzią jest:

1
1
0
2
2

Wyjaśnienie dla przypadku n = 15:
Z piętnastu wierzchołków możemy zbudować albo pięć trójkątów albo trzy czworokąty i jeden trójkąt. Otrzymujemy dwa sposoby.