Vadim is playing a niche game. This game has a side view, and everything takes place on an almost infinite rectangular grid of cells. You can place no more than one block in each cell. Vadim wants to build a wooden house for himself using the following algorithm:

As every player knows, you cannot just get stairs and slabs for free: they need to be crafted. To craft four stairs, six wooden blocks are used, and to craft six half-blocks, three wooden blocks are used:

Vadim has T worlds, in each of which he has N_i wooden blocks. In each world, he wants to build a house with the maximum volume out of the blocks. Help him find these volumes ant the sizes of the houses at which these volumes are achieved.

The first line of input contains an integer T — the number of worlds (1 ≤ T ≤ 1 000).

The next T lines of input contain integers N_i — the number of wooden blocks Vadim has in the i-th world (16 ≤ N_i ≤ 10⁹).

For each world, output three integers — the maximum possible volume of the house, and the width and height of a house at which this volume is achieved. It is guaranteed that an answer exists. If there are several answers, output any of them.