Question: Consider a Currency System in which there are notes of six denominations, namely, 1 cs, 2 cs, 5 cs, 10 cs, 50 cs, 100 cs. Write a program to compute smallest number of notes, if the sum of cs (N) is entered.

Input specification: The first number contains an integer T which is the total number of test cases followed by T numbers, each number containing an integer N separated by space.

Output specification: Display the smallest number of notes that will combine to give N.

Explanation: In the first sample input, 3 is the total number of test cases. 1200 is the first test case of the line. In order for the total notes the smallest, we start choosing the higher denomination which is 100 cs. Therefore, we can make 12 notes out of 1200 cs. The next number (550) can be chosen like: 5 from 100cs (500 cs) and 1 from 50cs (50 cs) whose total is 550 cs.