Minimum Number of Coins Problem

Dora, on her visit to India, decides to enjoy Indian cuisine where payments are accepted only in specific denominations. Your task is to help Dora obtain the minimum number of coins for a given amount using the available denominations of [1, 2, 5, 10, 20, 50, 100, 500, 1000]. The bank has an unlimited supply of these denominations.

Explanation:

For a provided amount, determine the least number of coins needed to make up that amount.

Input:

The first line contains an integer 'T', the number of test cases. Each of the next 'T' lines contains a single integer 'Amount'.

Output:

For each test case, output the minimum number of coins required on a new line.

Example:

Input:

2
70
121

Output:

2
3

Explanation:

For Amount = 70, coins of Rs. 50 and Rs. 20 can be used. For Amount = 121, coins of Rs. 100, Rs. 20, and Rs. 1 can be used.

Constraints:

• 1 <= T <= 100
• 1 <= Amount <= 105

Note:

It is guaranteed that a solution exists for each input Amount provided.