A. Legs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's another beautiful day on Farmer John's farm.

After Farmer John arrived at his farm, he counted $$$n$$$ legs. It is known only chickens and cows live on the farm, and a chicken has $$$2$$$ legs while a cow has $$$4$$$.

What is the minimum number of animals Farmer John can have on his farm assuming he counted the legs of all animals?

Input

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

Each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^3$$$, $$$n$$$ is even).

Output

For each test case, output an integer, the minimum number of animals Farmer John can have on his farm.

Example
Input
3
2
6
8
Output
1
2
2