Time Limit: 1s
Memory Limit: 256MB
Minh go shopping at the SS shop. The shop has currency denominations: 1$, 5$, 10$, 50$, 100$, 500$. Minh takes some items at the shop and pay an amount of 1000$.
Your task to devise a method to pay back amount to customer using fewest number of money notes.
The first line contains one single integer T (1 ≤ T ≤ 999) denoting the number of test cases.
Each of T next lines consists of only one single integer N (1 ≤ N ≤ 999) denoting the total value of the taken items.
For each test case, print a line containing one single integer denoting the number of money notes.
1 380
4
The shop has to pay back 620$ by giving 1 paper of 500$, 1 paper of 100$ and 2 papers of 10$.