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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
t= int(input())
for i in range(t):
    cnt=0
    n=int(input())
    while(n>=100):
        n-=100
        cnt+=1
    while(n>=50):
        n-=50
        cnt+=1
    while(n>=10):
        n-=10
        cnt+=1
    while(n>=5):
        n-=5
        cnt+=1
    while(n>=2):
        n-=2
        cnt+=1
    while(n>=1):
        n-=1
        cnt+=1
    print(cnt)

n = int(input())
def count (x) :
    m = 0  
    if (x - 100 >= 0) :
        m = int(x/100)
        x = x%100 
    if (x - 50 >= 0):
        m = int(x/50) + m
        x = x%50
    if (x - 10 >= 0):
        m = int(x/10) + m 
        x = x%10
    if (x - 5 >= 0) :
        m = int(x/5) + m 
        x = x%5
    if (x - 2 >= 0) :
        m = int(x/2) + m 
        x= x%2
    if (x - 1 >= 0) :
        m = 1 + m 
    return (m)    
    
for i in range (n) :
    x = int(input())
    p = count(x)
    print(p)
    


n=int(input())
for i in range(n):
    a=int(input())
    note=0
    while a!=0:
        if a>=100:
            a-=100
        elif a>=50:
            a-=50
        elif a>=10:
            a-=10 
        elif a>=5:
            a-=5 
        elif a>=2:
            a-=2
        else:
            a-=1 
        note+=1 
    print(note)
        


for _ in range(int(input())):
    l=[100,50,10,5,2,1]
    n=int(input())
    c=0
    for i in l:
        if(n>=i):
            r=n/i
            if(type(r)==int):
                print(r)
                break
            else:
                r=int(r)
                c+=r
                n=n-(i*r)
        if(n==0):
            break
    print(c)
            
                    
                
            
            


x=int(input())
lst=[1 , 2 , 5 , 10 , 50 , 100 ]
for i in range(x):
    y=int(input())
    c=5
    a=0
    while(y>0):
        if(y >= lst[c] ):
            y=y-lst[c]
            a=a+1
        else:
            c=c-1
    print(a)        


# cook your dish here
x=int(input())
lst=[1 , 2 , 5 , 10 , 50 , 100 ]
for i in range(x):
    y=int(input())
    c=5
    a=0
    while(y>0):
        if(y >= lst[c] ):
            y=y-lst[c]
            a=a+1
        else:
            c=c-1
    print(a)        

# cook your dish here
x=int(input())
lst=[1 , 2 , 5 , 10 , 50 , 100 ]
for i in range(x):
    y=int(input())
    c=5
    a=0
    while(y>0):
        if(y >= lst[c] ):
            y=y-lst[c]
            a=a+1
        else:
            c=c-1
    print(a)        

# cook your dish here
def notes(a):
  Q = [ 100, 50, 10,5,2,1]
  x ,b= 0,0
  for i in Q:
    b=a//i
    x += b
    a = a-i*b
  return x
n=int(input())
for i in range(n):
    m=int(input())
    print(notes(m))

# cook your dish here
t=int(input())
while t!=0:
    n=int(input())
    ct=0
    notes=[100,50,10,5,2,1]
    i=0
    while n:
        ct+=n//notes[i]
        n=n%notes[i]
        i+=1
    print(ct)
    t=t-1

t=int(input())
l=[100,50,10,5,2,1]
for _ in range(t):
    c=0
    n=int(input())
    i=0
    while n:
        c+=n//l[i]
        n=n%l[i]
        i=i+1
        
    print(c)

t=int(input())
l=[100,50,10,5,2,1]
for _ in range(t):
    c=0
    n=int(input())
    i=0
    while n:
        c+=n//l[i]
        n=n%l[i]
        i=i+1
        
    print(c)
    


#Read the number of test cases.
T = int(input())

for tc in range(T):
# Read integers a and b.
    n = int(input())
    count = 0
    while n:
        count += n//100
        n=n%100
        count += n//50
        n=n%50
        count += n//10
        n=n%10
        count += n//5
        n=n%5
        count += n//2
        n=n%2
        count += n//1
        n=n%1
    print(count)    


# cook your dish here
a=[100,50,10,5,2,1]
for i in range(int(input())):
    n=int(input())
    c=0
    for i in a:
        if n!=0:
            if n//i!=0:
                c+=n//i
                n-=((n//i)*i)
        else:
            break 
    print(c)

# cook your dish here
T = int(input())

avail = [100,50,10,5,2,1]

for i in range(T):
    N = int(input())
    notes = []
    for note in avail:
        if note > N:
            continue
        else:
            c = N//note
            notes.append(c)
            N = N % note
    print(sum(notes))

t=int(input())
i=0
while i<t:
	n=int(input())
	c=0
	z=0
	if n>=100:
		a=n//100
		n=n-(100*a)
		z=a
	if n>=50:
		b=n//50
		n=n-(50*b)
		z=z+b
	if n>=10:
		c=n//10
		n=n-(10*c)
		z=z+c
	if n>=5:
		d=n//5
		n=n-(5*d)
		z=z+d
	if n>=2:
		e=n//2
		n=n-(2*e)
		z=z+e
	if n==1:
		print(z+1)
	else:
		print(z)
	i+=1

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)

# cook your dish here
t=int(input())
for i in range(t):
    s=0
    n=int(input())
    l=[100,50,10,5,2,1]
    k=n
    while(k!=0):
        for j in range(len(l)):
             s=s+(k//l[j])
             k=k%l[j]
        print(s)
       
       


# cook your dish here
t=int(input())
for i in range(t):
    s=0
    n=int(input())
    l=[100,50,10,5,2,1]
    k=n
    it=0
    total=0
    l1=[]
    while(sum(l1)!=n):
        r=k//l[it]
        total=total+r
        if(r!=0):
            l1.append(r*l[it])
            k=k%l[it]
        it+=1
    print(total)
    


t= int(input())

for i in range(t):
    a=int(input())
    notes=[100,50,10,5,2,1]
    c=0
    while a>=1:
        for i in notes:
            c=c+a//i
            a=a%i
       
    print(c)

# cook your dish here
t=int(input())
cl=[1,2,5,10,50,100]
l=len(cl)
for i in range(t):
    a=int(input())
    n=0
    w=1
    while(a%cl[-w]!=0):
        n=n+a//cl[-w]
        a=a%cl[-w]
        w=w+1
    n=n+a//cl[-w]
    print(n)
        


t=int(input())
l=[100,50,10,5,2,1]
for k in range(t):
    c=0
    s=0
    n=int(input())
    for j in range(6):
        s=int(n/l[j])
        c=c+s
        n=n-(s*l[j])
    print(c)

# cook your dish here
t=int(input())
for i in range(t):
    P=[100,50,10,5,2,1]
    n=int(input())
    count=0
    for i in P:
        if(n>=i):
            count=count+n//i
            n=n%i
    print(count)        

# cook your dish here
for i in range(int(input())):
    num=int(input())
    cnt=0
    lst=[100,50,10,5,2,1]
    for i in range(len(lst)):
        cnt+=num//lst[i]
        num=num%lst[i]
    print(cnt)

# cook your dish here
t = int(input())
for i in range(t):
    n = int(input())
    c=0
    sum=0
    if(n>=100):
        c = c + n//100
        n = n%100
    if(n>=50):
        c = c + n//50
        n=n%50
    if(n>=10):
        c = c+ n//10
        n = n%10
    if(n>=5):
        c = c + n//5
        n = n%5
    if(n>=2):
        c = c + n//2
        n = n%2
    if(n>=1):
        c = c+ n//1
        
    print(c)
        


# cook your dish here
n=int(input())
l1=[]
for i in range(0,n):
    l1.append(int(input()))
for item in l1:
    num1=0
    a=item%100
    if(a==0):
        num1+=(item/100)
    else:
        num1+=((item-a)/100)
        b=a%50
        if(b==0):
            num1+=(a/50)
        else:
            num1+=((a-b)/50)
            c=b%10
            if(c==0):
                num1+=(b/10)
            else:
                num1+=((b-c)/10)
                d=c%5
                if(d==0):
                    num1+=(c/5)
                else:
                    num1+=((c-d)/5)
                    e=d%2
                    if(e==0):
                        num1+=(d/2)
                    else:
                        num1+=((d-e)/2)
                        f=e%1
                        if(f==0):
                            num1+=(e)
    print(int(num1))