#OJ1753. d 钞票

d 钞票

d 钞票

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

小K是个不折不扣的土豪,因为他手里有着花不完的各种钞票。每到周末小K去便利店买东西时,就会带上一大把钞票。问题来了,假设小K和便利店都有各种面值(1元、5元、10元、20元、50元、100元)的足量钞票,当小K买x元东西时,双方至少共需要使用几张钞票?

Input

第一行T(T<5000),表示用例有T组 后面T行,每行一个正整数x(0<x<10^9),为小K的花费

Output

每组用例输出一行,为钞票数

Sample Input

2
1
9

Sample Output

1
2

HINT

Append Code

Source