题目描述

由于大多数计算机都是二进制机器，2 的幂以及只涉及两个数值的问题对计算机科学家来说都很重要。

一些 2 的幂在十进制表示下，其末尾若干位只包含数字 1 和 2。例如：

它的最后两位为 12；又如 $2^{89}$ 的末尾四位为 2112。

可以证明：对于任意正整数 $R$，都存在一个 $2^K$，使得它的最后 $R$ 位全部由数字 1 和 2 组成。

给定 $R$，请找出满足上述条件的最小正整数 $K$。

输入格式

第一行一个整数 $N$：

表示测试数据组数。

接下来 $N$ 行，每行一个整数 $R$：

输出格式

对于第 $i$ 组数据，输出一行三个整数：

i R K

其中：

• $i$ 为数据编号，从 1 开始；
• $R$ 为输入值；
• $K$ 为满足 $2^K$ 的最后 $R$ 位均为 1 或 2 的最小正整数。

样例输入

6
1
2
4
5
7
15

样例输出

1 1 1
2 2 9
3 4 89
4 5 589
5 7 3089
6 15 11687815589