题目描述

这是 Farmer John 农场上又一个美好的一天。

Farmer John 到达农场后，数到了 $n$ 条腿。已知农场里只有鸡和牛：鸡有 $2$ 条腿，牛有 $4$ 条腿。

假设 Farmer John 数到了农场里所有动物的腿，请你计算他农场里可能拥有的最少动物数量。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^3$），表示测试用例数量。

接下来 $t$ 行，每行一个整数 $n$（$2 \le n \le 2 \cdot 10^3$，且 $n$ 为偶数），表示腿的总数。

输出格式

对每个测试用例，输出一行一个整数：在满足总腿数为 $n$ 的前提下，可能的最少动物数量。

样例

输入

3
2
6
8

输出

1
2
2