Minh đi mua sắm tại cửa hàng SS. Cửa hàng có các mệnh giá tiền: 1$, 5$, 10$, 50$, 100$, 500$. Minh mua một số mặt hàng trong cửa hàng và trả số tiền là 1000$. Nhiệm vụ của bạn là tìm ra cách trả lại tiền thừa cho Minh bằng số lượng tờ tiền ít nhất.

Input:

Dữ liệu đầu vào là nhiều dòng, trong đó dòng đầu tiên biểu thị số lượng lần mua. N dòng tiếp theo mỗi dòng biểu thị duy nhất một số nguyên N (1 ≤ N ≤ 999) là tổng giá trị của các mặt hàng Minh đã mua.

Output:

Dữ liệu đầu ra là các dòng, mỗi dòng là một số nguyên duy nhất, biểu thị số lượng tờ tiền ít nhất mà cửa hàng phải trả lại.

Giải thích:

Với 380 cửa hàng cần trả lại 620$ bằng cách sử dụng 1 tờ 500$, 1 tờ 100$, và 2 tờ 10$. Nên kết quả là 4

Ví dụ:

Input:

2
380
1

Output:

4
15