Tại ngân hàng có các mệnh giá bằng 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000. Tổng số tiền cần đổi có giá trị bằng N. Hãy xác định xem có ít nhất bao nhiêu tờ tiền sau khi đổi tiền?

Input Format

Dòng đầu tiên là số lượng bộ test T (T ≤ 50). Mỗi test gồm 1 số nguyên N (1 ≤ N ≤ 10^9).

Constraints

.

Output Format

Với mỗi test, in ra đáp án trên một dòng.

Ví dụ:

Dữ liệu vào

2
70
121

Dữ liệu ra

2
3