QUICKTRN - Quick Transaction
Your mother sends you to market to buy some stuff which costs Rs. X, you simply need to find the minimum no. of currency denominations required to complete the transaction. Assume that the seller only takes exactly Rs. X, not more nor less than that.
Also assume standard denominations of 1, 2, 5, 10, 20, 50, 100, 500 and 1000. Also consider that each denomination is in infinite supply.
Input
First line denotes T, no. of test cases Next T lines flows each line contains one integer X, the amount needs to be paid.
Output
Print the min. no. of denominations required for buying product for each test case.
Constraints
1<=T<=1000
1<=X<=10^9
Example
Input:3
Output:
305
67
1054
4
2
Added by: | Rajesh Kumar |
Date: | 2014-11-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |