Ngân hàng kì lạ

Ở một ngân hàng kì lạ, bạn có thể đổi một đồng \(x\) xu để lấy ba đồng mới có giá trị \(\lfloor \frac{x}{2} \rfloor\) xu, \(\lfloor \frac{x}{3} \rfloor\) xu và \(\lfloor \frac{x}{4} \rfloor\) xu. Với \(y\) là một số thực, kí hiệu \(\lfloor y \rfloor\) là số nguyên lớn nhất không vượt quá \(y\).

Bạn đang có \(T\) đồng xu. Với mỗi đồng xu, nếu đổi theo cách tối ưu (có thể đổi tiếp các đồng xu mới nhận được, hoặc dừng lại ở bất kì lúc nào), hãy tính số tiền lớn nhất bạn có thể thu được từ đồng xu đó.

Input

• Dòng đầu tiên gồm một số nguyên \(T\) (\(1 \le T \le 10\)).

• \(T\) dòng tiếp theo, mỗi dòng gồm một số nguyên \(x\) (\(1 \le x \le 10^9\)) thể hiện giá trị của đồng xu bạn đang có.

Output

In ra \(T\) dòng, mỗi dòng gồm một số nguyên là số tiền lớn nhất có thể thu được từ đồng xu tương ứng.

Example

Input:

2
12
2

Output:

13
2

Note

• Đồng \(12\) xu: Đổi đồng \(12\) xu sẽ được ba đồng xu \(6\), \(4\) và \(3\). Tiếp tục đổi bất kì đồng xu mới nào cũng không giúp tổng số tiền tăng thêm, nên tổng tối ưu là \(6 + 4 + 3 = 13\).

• Đồng \(2\) xu: Đổi đồng \(2\) xu sẽ được ba đồng xu \(1\), \(0\) và \(0\), có tổng bằng \(1 < 2\), nên tốt nhất là không đổi, giữ nguyên giá trị \(2\).