This page is still under construction.

Parts of this page are still being built. What you see may change.

Pizza Oven

Interview

Time limit0.25sMemory limit256 MB

Summary
Find the fewest button presses (ADDH, ADDT, MINT, ADDO, MINO) to reach a target time, breaking ties by lexicographically smallest press counts.
Level

Medium6 of 10

Topics
Greedy, Math, Implementation, Brute force
Solved
No attempts yet

Problem

There is an electric oven for baking pizza. You want to put ingredients in this oven and run it for exactly NN minutes. The oven has five buttons that change the operating time. Initially the oven's time is set to 0 minutes. If pressing a button that decreases the time makes the time less than 0 minutes, it is set to 0 minutes. Let tt be the time currently set on the oven and t′t' the time after pressing a button. Each button works as follows.

  • ADDH: t′=t+60t' = t + 60
  • ADDT: t′=t+10t' = t + 10
  • MINT: t′=t−10t' = t - 10
  • ADDO: t′=t+1t' = t + 1
  • MINO: t′=t−1t' = t - 1

For example, to set 58 minutes, you can press ADDO (+1 minute) 58 times. But if you press ADDH (+60 minutes) once and then MINO (-1 minute) twice, you can make 58 minutes in 3 presses. To set 42 minutes, you can press ADDH, MINT, MINT, ADDO, ADDO in that order, 5 presses. You can also do it in 6 presses with ADDT, ADDT, ADDT, ADDT, ADDO, ADDO, but you want to press the buttons as few times as possible.

Given the time to set, write a program that finds the minimum number of button presses needed to make that time and the method to do it.

Input

The input consists of TT test cases. Each test case is one line, giving the time NN to set as an integer in minutes.

Output

For each test case, print five integers on one line separated by spaces. These integers are the number of times to press the ADDH, ADDT, MINT, ADDO, and MINO buttons to make the given time. If there are multiple ways to press the buttons the minimum number of times, print the lexicographically smallest one.

When several methods have the same number of presses, the one with fewer ADDH presses comes first lexicographically; if the number of ADDH presses is the same, the one with fewer ADDT presses comes first. If the number of ADDT presses is the same, the one with fewer MINT presses comes first; if the number of MINT presses is the same, the one with fewer ADDO presses comes first; if the number of ADDO presses is the same, the one with fewer MINO presses comes first.

Constraints

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤10,000,0001 \le N \le 10,000,000

Examples1

  1. Example 1

    Input
    3
5
12
27
    Expected output
    0 0 0 5 0
0 1 0 2 0
0 3 0 0 3