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