Choosing a Fleet of Vehicles

Each query gives a total number of wheels; form a fleet from unlimited two-wheeled and four-wheeled vehicles. Two options are different only if the number of vehicles of some type differs; arrangements are not counted.

输入格式

The first line contains n, followed by n values of wheels; 1≤n≤100000, 1≤wheels[i]≤1000000.

输出格式

Output n lines with the number of options, in input order.

样例 1

输入：

3
4 5 6

输出：

2
0
2

样例 2

输入：

3
1 2 3

输出：

0
1
0

样例 3

输入：

3
8 10 12

输出：

3
3
4

样例说明

The outputs of the three public examples are, in order: 2 / 0 / 2; 0 / 1 / 0; 3 / 3 / 4. These answers have been checked by independent enumeration or direct simulation.