Đội tình nguyện viên HUTECH đang phát triển một hệ thống máy bán hàng tự động. Máy đang ở giai đoạn thử nghiệm và sẽ không trả lại tiền thừa, bạn phải trả đúng số tiền món hàng cần mua (không thừa, cũng không thiếu).

Bờm có kế hoạch mua một món đồ bằng máy bán hàng tự động này. Bờm là một đại gia có rất nhiều tiền xu, nhưng anh ta lại không thích mang nhiều tiền ra đường vì đồng xu khá nặng. Mặt khác, Bờm chỉ biết món đồ mình cần mua có giá tiền không vượt quá C, chứ không biết giá chính xác của nó.

Bờm có đủ các đồng xu với tất cả mệnh giá không vượt quá C, đồng thời số lượng đồng xu mỗi mệnh giá cũng đủ lớn (có thể coi là vô hạn). Bờm muốn biết mình cần mang ít nhất bao nhiêu đồng xu để chắc chắn mua được món hàng đó.

• Dòng thứ hai chứa một số nguyên dương T là số bộ dữ liệu (1 \leq T \leq 10).
• T dòng tiếp theo, dòng thứ i chứa một số nguyên dương C_i duy nhất là giá tiền tối đa của món đồ Bờm cần mua đã đề cập trong đề bài (C_i \leq 10^{18}).

Đưa ra kết quả lần lượt các bộ dữ liệu theo thứ tự từ 1 đến T. Với bộ dữ liệu thứ i, kết quả được đưa ra trên 2 dòng:

• Dòng đầu tiên chứa số lượng đồng xu ít nhất có thể Bờm cần mang theo.
• Dòng thứ hai chứa danh sách mệnh giá các đồng xu mà Bờm sẽ mang theo.

Nếu có nhiều cách chọn đồng xu thỏa mãn, bạn chỉ cần chọn một cách bất kỳ.

• 10% số test ứng với 10% số điểm có C_i \leq 10.
• 20% số test ứng với 20% số điểm có C_i \leq 20.
• 70% số test ứng với 70% số điểm còn lại không có ràng buộc gì thêm.

- Với bộ dữ liệu đầu tiên:

- Với bộ dữ liệu thứ hai: