HZNUOJ

【C系列3.3】发奖金

Tags:   
Time Limit:  1 s      Memory Limit:   32 MB
Submission:4533     AC:2695     Score:10.00

Description

终于到了发奖金的日子,经过很多次的ACM比赛,每个同学都有许许多多的奖金,于是单总今天去银行取钱发奖金。为了使钱包轻一点,单总希望,用最少张数的钱来凑足总奖金。

Input

第一行有一个正整数T表示有T组数据,接下来T行每行有一个正整数n(0 <= n <= 10000)表示总奖金数。

Output

每组数据输出一行,代表凑足总奖金数所需的最少张数的纸币。(纸币面额有100元,50元,10元,5元,1元)。

Samples

input
2 15 351
output
2 5

Author

YE, Lei