Tèo đang đứng ở ô 0 trên một đường tọa độ. Mục tiêu của Tèo là đạt đến ô $n$.

Trong một bước, Tèo có thể di chuyển thêm 2 ô hoặc 3 ô sang trái hoặc sang phải (Ví dụ: Nếu tọa độ hiện tại của Tèo là $x$, nó có thể trở thành $x-3,x-2,x+2$ hoặc $x+3$ ).

Lưu ý rằng tọa độ mới có thể trở thành số âm.

Nhiệm vụ của Tèo là tìm số bước tối thiểu cần thiết để đi từ ô 0 đến ô $n$. Hãy giúp Tèo nhé

Input

Dòng đầu tiên của đầu vào chứa một số nguyên $t$ $(1\le t\le {10}^4)$ — số lượng trường hợp.

Sau đó, $t$ dòng mô tả các trường hợp.

Dòng thứ $i$ của những dòng này chứa một số nguyên $n$ $(1\le n\le {10}^9)$ - mục tiêu của trường hợp thứ $i$.

Output

Đối với mỗi trường hợp, in một số nguyên - số bước tối thiểu cần thiết để có được từ ô 0 đến ô $n$ cho trường hợp thử nghiệm tương ứng.

Example

Input1

4
1
3
4
12

Output1

2
1
2
4

Note:

• Với $n=1$, Tèo cần tiến 3 bước và lùi 2 bước. Như vậy, Tèo cần di chuyển tối thiểu là 2 bước.