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≤t≤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≤n≤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.