Nothing's ever been the same since... that summer with her.— Shizuku Hoshikawa

Kaori wants to spend the day with Shizuku! However, the zoo is closed, so they are visiting Farmer John's farm instead.

At Farmer John's farm, Shizuku counts $n$ legs. It is known that only chickens and cows live on the farm; a chicken has $2$ legs, while a cow has $4$.

Count how many different configurations of Farmer John's farm are possible. Two configurations are considered different if they contain either a different number of chickens, a different number of cows, or both.

Note that Farmer John's farm may contain zero chickens or zero cows.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 100$)  — the number of test cases.

The only line of each test case contains a single integer $n$ ($1\leq n \leq 100$).

Output

For each test case, output a single integer, the number of different configurations of Farmer John's farm that are possible.

Note

For $n=4$, there are two possible configurations of Farmer John's farm:

• he can have two chickens and zero cows, or
• he can have zero chickens and one cow.

It can be shown that these are the only possible configurations of Farmer John's farm.

For $n=3$, it can be shown that there are no possible configurations of Farmer John's farm.

Samples

5
2
3
4
6
100

1
0
2
2
26