Per có ~32~ đồng xu kì diệu, kí hiệu là ~c_1, c_2, \ldots, c_{32}~, trong đó:

• ~c_1 = 2~
• ~c_2 = 3~
• ~c_3 = 5~
• ~c_i = c_{i-1} + c_{i-2} + c_{i-3}~ với mọi ~i \ge 4~

Với mỗi số nguyên ~x~ cho trước, Per muốn tìm xem nhiều nhất có thể chọn ra bao nhiêu đồng xu sao cho tổng giá trị của chúng đúng bằng ~x~. Mỗi đồng xu chỉ được chọn nhiều nhất một lần.

Các bạn học viên hãy thử giúp Per nhé!

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~T~ — số bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~ — tổng cho trước.

Kết quả

Với mỗi bộ test, in ra trên một dòng số lượng đồng xu nhiều nhất chọn được. Nếu không tồn tại cách chọn nào thì in ra HETCUU.

Ví dụ

Đầu vào:

3
3
5
11

Đầu ra:

1
2
HETCUU

Giải thích:

• ~x = 3~: chỉ có một cách là chọn ~c_2 = 3~.
• ~x = 5~: có thể chọn ~c_3 = 5~ (một đồng xu) hoặc ~c_1 + c_2 = 2 + 3~ (hai đồng xu), nên đáp án là ~2~.
• ~x = 11~: không có cách chọn nào.

Giới hạn

• ~1 \le T \le 10^3~
• ~1 \le x \le 10^9~

Tổng giá trị của cả ~32~ đồng xu là ~551\,593\,712~. Chia ~32~ đồng xu thành hai nửa ~16~ đồng: với mỗi nửa chỉ có ~2^{16}~ tập con, và ta chỉ cần lưu số đồng xu nhiều nhất ứng với mỗi tổng.