落于现象

题目描述

终有一日将升入超验的王国。 或迟或早将摆脱痛苦的现象。 但在此之前，还请去证明。 这圆锥体上冰凉又甜蜜的假说。

在沙滩上，37正在观测现象世界因为“暴雨”而产生的异常。沙滩上的几何图形正在不断地分裂出新的图形。具体地说，对于每秒：

1. $1$ 个立方体会分裂出 $1$ 个锥体，$1$ 个立方体和 $1$ 个圆柱体。
2. $1$ 个锥体会分裂出 $2$ 个立方体和 $2$ 个圆柱体。
3. $1$ 个圆柱体会分裂出 $1$ 个立方体和 $1$ 个锥体。

同时，每个几何体分裂出新的几何体之后，它自身并不会消失，并且会参与下一次分裂。第 $0$ 秒时，沙滩上有锥体，立方体和圆柱体各 $1$ 个，37想问你，$x$ 秒之后沙滩上各个图形各有多少个？由于37知道这个数可能很大，你只需要回答37他们是奇数还是偶数即可。

输入格式

输入包含多组测试数据，第一行为一个整数 $T$，表述测试数据组数。 每组测试数据包含 $1$ 行，为一个整数 $x$。

数据范围

$1\le x,T \le 10^6$

输出格式

对于每次询问，输出三个整数 $x,y,z$，分别表示立方体，锥体和圆柱体数量的奇偶性，奇数为1，偶数为0。

样例 #1

样例输入 #1

3
3
4
114514

样例输出 #1

1 1 1
1 1 0
1 1 0