Consider a currency system in which there are notes of six denominations, namely, Rs. 1, Rs. 2, Rs. 5, Rs. 10, Rs. 50, Rs. 100.
If the sum of Rs. N is input, write a program to computer smallest number of notes that will combine to give Rs. N.
-----Input-----
The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer N. 
-----Output-----
For each test case, display the smallest number of notes that will combine to give N, in a new line.
-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 1000000
-----Example-----
Input
3 
1200
500
242
Output
12
5
7
n=int(input())
for i in range(n):
    t=int(input())
    sum=0
    while(t):
        t1=t//100
        sum+=t1
        t=t%100
        if t>0:
            t1=t//50
            sum+=t1
            t=t%50
        if t>0:
            t1=t//10
            sum+=t1
            t=t%10
        if t>0:
            t1=t//5
            sum+=t1
            t=t%5
        if t>0:
            t1=t//2
            sum+=t1
            t=t%2
        if t>0:
            t1=t//1
            sum+=t1
            t=t%1
    print(sum)
n=int(input())
for i in range(n):
    t=int(input())
    sum=0
    while(t):
        t1=t//100
        sum+=t1
        t=t%100
        if t>0:
            t1=t//50
            sum+=t1
            t=t%50
        if t>0:
            t1=t//10
            sum+=t1
            t=t%10
        if t>0:
            t1=t//5
            sum+=t1
            t=t%5
        if t>0:
            t1=t//2
            sum+=t1
            t=t%2
        if t>0:
            t1=t//1
            sum+=t1
            t=t%1
    print(sum)