Laundry Owner Donghyuk

Interview

Time limit1sMemory limit128 MB

Summary

Given a number of cents, output the minimum count of quarters, dimes, nickels, and pennies using a greedy coin breakdown.

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

Problem

Donghyuk runs a laundry in the United States and recently hired a part-time worker named Liam. Liam often makes mistakes when giving change. For example, when he should give 0.50 dollars, he might hand over 5.00 dollars instead.

Donghyuk wants to write a program to help Liam, but he does not have time to code it himself. Given an amount of change, write a program that computes how many quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent) Liam should give to the customer.

The amount of change is always at most 5.00 dollars, and the total number of coins given to the customer must be minimized. For example, if 1.24 dollars must be given as change, the customer receives 4 quarters, 2 dimes, 0 nickels, and 4 pennies.

Input

The first line contains the number of test cases T.

Each of the next T lines contains one integer C, the amount of change for that test case in cents. One dollar is 100 cents, and 1 <= C <= 500.

Output

For each test case, print one line containing the number of quarters, dimes, nickels, and pennies needed, in that order, separated by spaces.

Examples1

Example 1
Input
```
3
124
25
194
```
Expected output
```
4 2 0 4
1 0 0 0
7 1 1 4
```