SPOJ in Gyumri

   Juliet reads an interesting sci-fi book. In one chapter, the main character needs to solve a problem of maximizing the utilization of cargo spaceships. The ships transport valuable items that have the form of D-dimensional mesh with the size of 3 nodes in each dimension. The nodes are formed by balls of the same weight. The connections between balls are so light that their weight is negligible compared to the weight of balls. This means that the weight of any item is determined solely by the number of its nodes. On the other hand, the value of such an item is equal to the number of nodes plus the number of connections.

   Each spaceships has a limited tonnage and we want to maximize the total value of items that may be stored in the ship without exceeding the tonnage. Your task is to decide what items of what dimension should be loaded to maximize their total value, providing that we have an unlimited supply of items of all dimensions.

Input

   The first line of the input contains the number of test cases N . Each test case then consists of a single line containing one positive integer number K < 10 000 000 giving the ship cargo capacity.

Output

   For each test case, print one line containing space-separated non-negative numbers X_m X_m−1. . . X₁ X₀, where X_m > 0 and X_i (0 ≤ i ≤ m) is the number of items of the i-th dimension that we need to store to maximize their total value.

Examples