Making Change

Interview

Time limit1sMemory limit1024 MB

Summary

For each pair of cost and payment amounts, compute the change and break it into the fewest $50, $20, $10, $5, and $1 bills.

Level: Easy2 of 10
Topics: Greedy, Math, Implementation, Simulation
Solved: No attempts yet

Problem

Anakin Skywalker is leaving Tatooine, but before he can go he must program a droid to do his old job of making change for customers at Watto's junk business. Given the price of an item and the payment, determine the correct change using $50, $20, $10, $5, and $1 bills. You don't have to worry about having change on hand, because Watto always keeps the change.

Input

A positive integer, n, on the first line indicating the number of data sets to follow. Each data set will consist of two positive numbers. The first is the cost to the customer and the second is the payment made by the customer. The payment will always be greater than the cost.

Output

For each data set print the correct change on one line using the format

v-$50, w-$20, x-$10, y-$5, z-$1

where v, w, x, y, z are the number of bills needed to make the correct change. Of course, the correct change will always use larger bills when possible (i.e., 1-$5 not 5-$1)

Examples1

Example 1

Input

3
1894.77 2000.00
77.15 100.40
25.50 100.00

Expected output

2-$50, 0-$20, 0-$10, 1-$5, 0-$1
0-$50, 1-$20, 0-$10, 0-$5, 3-$1
1-$50, 1-$20, 0-$10, 0-$5, 4-$1