An là một đại gia có tiếng trong làng và hiện tại anh ấy đang có \(n\) đô la trong tài khoản ngân hàng. Vì sợ bị các hacker lừa đảo rút hết tiền của mình (do thế giới ngày càng phức tạp) nên anh ấy quyết định đi rút tiền mặt.
Cụ thể như sau, ở cây ATM của ngân hàng chỉ cho phép anh ấy mỗi lần rút tiền chỉ có một trong các mệnh giá như sau: \(1,5,10,20,100\) đô la mà thôi.
Hỏi anh ấy cần ít nhất bao nhiêu lần rút thì hết toàn bộ số tiền anh ấy có trong ngân hàng ?

Input

• Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 100)\) - Thể hiện số testcase
• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(n(1\le n\le 10^9)\) thể hiện số tiền An có trong ngân hàng

Output

• Ứng với mỗi giá trị của \(n\), hãy in kết quả ra màn hình.

Example

2
125
43

3
5