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

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

Output

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

Example

2
70
121

2
3