Question

Rahul's Farm

3

2

4

6

1

1

2

Test case 1: With N = 2 legs present, the only possibility is for there to be one chicken and no cows; for one animal in total.

Test case 2: With N = 4 legs present, either there should be one cow or two chickens. The minimum is thus 1.

After a long and fulfilling career, Rahul has decided to retire to a farm out in the countryside.

This farm has several cows and chickens, but Rahul doesn't know exactly how many of each there are - he can only see that there are N legs in total across all the animals.

Note that each cow has 4 legs and each chicken has 2 legs, and it is guaranteed that N is even.

With N legs in total, what's the **minimum** possible number of animals that can be present on the farm?

Input

The first line of the input contains a single integer T, denoting the number of test cases.

The each line of the test case contains a single integer N, denoting the number of legs.

1 ≤ T ≤ 1000

2 ≤ N ≤ 2000

The each line of the test case contains a single integer N, denoting the number of legs.

**Constraints**1 ≤ T ≤ 1000

2 ≤ N ≤ 2000

**Note**: N is even.Output

For each test case, output on a new line the minimum possible number of animals that can be present on the farm.

Example

**Sample Input**

3

2

4

6

**Sample Output**

1

1

2

**Explanation**

Test case 1: With N = 2 legs present, the only possibility is for there to be one chicken and no cows; for one animal in total.

Test case 2: With N = 4 legs present, either there should be one cow or two chickens. The minimum is thus 1.