湊出金額的最少代幣數

題目敘述

校慶園遊會的攤位只收四種代幣，面額分別是 1、5、10、50。

每次給你一個金額 n，請問要剛好湊出 n，最少需要幾枚代幣？

輸入格式

第一行是一個正整數 m，代表測試資料的組數。 接下來 m 行，每行一個正整數 n。

輸出格式

每組測試資料輸出一行，內容為所需的最少代幣數。

限制

• 1 ≤ m
• 1 ≤ n < 1000

範例

範例 1

輸入

7
21
50
123
984
120
361
999

輸出

3
1
7
26
4
9
28

說明

21=10+10+1，需要 3 枚；50 本身就是一枚 50 的代幣，只需 1 枚。