You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

今天又是美好的一天，雷王打算去银行取点钱去吃好吃的，雷王的账户里总共有$m$元，他想把所有的余额都取出来。银行只提供金额为$1, 5, 10, 20, 100$的纸币，但是这家银行很缺德，他要求你自己去计算你需要取的每种纸币的数量，然后才会给你对应数量的纸币。

雷王非常懒，他不想要带着太多的纸币去玩耍，于是他习惯性的将任务推给ZJ学姐，但众所周知学姐又在装弱。因此，你能帮帮学姐怎么样取可以在取完所有的余额的前提下，保证取出纸币的总数量最少咩？

Input Format

在第一行中输入一个正整数$t$，代表测试用例的个数。 对于每组测试用例：
在一行中输入一个正整数$m$，代表雷王的账户余额。

Output Format

在一行中输出一个正整数$ans$，代表纸币最少的总数量。

1
125

3

1
1000000000

10000000