终于到了发奖金的日子，经过很多次的ACM比赛，每个同学都有许许多多的奖金，于是单总今天去银行取钱发奖金。为了使钱包轻一点，单总希望，用最少张数的钱来凑足总奖金。
第一行有一个正整数T表示有T组数据，接下来T行每行有一个正整数n（0 <= n <= 10000）表示总奖金数。
每组数据输出一行，代表凑足总奖金数所需的最少张数的纸币。（纸币面额有100元，50元，10元，5元，1元）。