Trên trục \(\text{Ox}\), bạn đang đứng ở vị trí \(0\).

Ở mỗi bước, bạn có thể tiến lên hoặc lùi xuống \(2\) bước hoặc \(3\) bước.

Ví dụ: Hiện tại bạn đang đứng ở vị trí \(x\), vậy thì ở bước tiếp theo bạn có thể đến \(1\) trong \(4\) vị trí: \((x+2),(x-2),(x+3),(x-3)\).

Yêu cầu:
Mục tiêu của bạn là đến được vị trí \(n\). Tìm số lượng bước ít nhất để thực hiện điều đó.

Input

• Dòng đầu: \(t\) - số test \((1 \le t \le 5\times 10^5)\)
• \(t\) dòng sau: mỗi dòng chứa một số \(n\) \((n \in \mathbb{N}^*, n \le 10^{18})\)

Output

• Ứng với mỗi test, in ra đáp án cần tìm.

Example

4
1
3
4
12

2
1
2
4