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
305
67
105

Output:

4
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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.