Đội tình nguyện viên Free Contest đ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á , 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á , đồ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ữ liệu vào:
Dòng thứ hai chứa một số nguyên dương là số bộ dữ liệu ;
dòng tiếp theo, dòng thứ chứa một số nguyên dương duy nhất là giá tiền tối đa của món đồ Bờm cần mua đã đề cập trong đề bài .
Dữ liệu ra:
Đưa ra kết quả lần lượt các bộ dữ liệu theo thứ tự từ đến . Với bộ dữ liệu thứ , kết quả được đưa ra trên 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ỳ.
Ví dụ:
Dữ liệu vào:
2
5
10
Dữ liệu ra:
3
1 1 3
4
1 1 3 6
Giải thích:
Với bộ dữ liệu đầu tiên:
Giá tiền món hàng
Danh sách mệnh giá các đồng xu Bờm chọn
đồng
đồng
Với bộ dữ liệu thứ hai:
Giá tiền món hàng
Danh sách mệnh giá các đồng xu Bờm chọn
đồng
đồng
Giới hạn:
số test ứng với số điểm có ;
số test ứng với số điểm có ;
số test ứng với số điểm còn lại không có ràng buộc gì thêm.
