## Problem: Minimum Notes Required

John works in RS Software and today he is supposed to receive his salary. RS Software pays its employees in cash. However, John’s wallet has one drawback. His wallet can contain no more than M notes or coins. Taking his case into consideration, his boss pays him his salary by the minimum notes possible. However John may have to leave out some money. Tell John how much money will he have to lose.

Note: The values of notes or coins available are 1000, 500, 100, 50, 20, 10, 5, 2 and 1.

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of a single line containing two space separated integers N and M denoting John’s salary and the maximum number of notes his wallet can hold, respectively.

Output:

Corresponding to each test case, print the desired output in a single line.

Constraints:

1<=T<=20

1<=N<=100000

1<=M<=1000

Example:

Input:

3

1712 4

1023 2

2341 3

Output:

12

3

241

Implement: Python 2.7

coins = [1000, 500, 100, 50, 20, 10, 5, 2, 1] def get_remain(n, m, i): if m == 0: return n if n <= 0: return 0 if n >= coins[i]: n -= coins[i] return get_remain(n, m-1, i) else: return get_remain(n, m, i+1) if __name__ == '__main__': t = input() for _ in range(t): n,m = map(int, raw_input().split()) print get_remain(n, m, 0)

## Reply