tourist 构思了一种新的哈希函数来存储管理员记录，并邀请你来帮助他构建它！他的哈希函数 $\phi(n)$ 将输出一个整数，并且需要以下信息：$l$、$r$ 和 $N$，其中 $l$ 表示 $n$ 的最左侧位，$r$ 表示 $n$ 的最右侧位，$N$ 表示 $n$ 中 1 的个数。

目前管理员记录并不多，所以我们暂时假设使用无符号 32 位数字系统。你的任务是根据记录数量 $k$ 以及每个记录的唯一标识符 $n$，为 tourist 提供他哈希函数所需的三个组成部分。顺便说一下，请忽略他哈希算法的荒谬之处。遗憾的是，tourist 从未上过正式的计算机科学课程。

输入格式

第一行包含记录数量 $k$，$1 \le k \le 500$。

接下来的 $k$ 行，每行包含一个整数，表示记录标识符 $n$，$0 \le n < 2^{31}$。

你可以假设所有输入均以十进制给出，你需要将它们转换为 32 位无符号整数，以获取每个 $n$ 的 $l$、$r$ 和 $N$。

输出格式

对于每条输入记录，在每一行打印三个以空格分隔的整数，分别表示 $n$ 的最左侧位 $l$、$n$ 的最右侧位 $r$ 以及 $n$ 中 1 的个数 $N$。

如需进一步说明，请参阅下方第一个样例的解释。

样例

输入 1

1
8

输出 1

0 0 1

输入 2

3
45
68
23

输出 2

0 1 4
0 0 2
0 1 4

说明

对于第一个样例，8 表示为 0x00000008（为简便起见用十六进制书写）。因此，最左侧位为 0，最右侧位为 0，1 的个数为 1。