F-Checkpoints_牛客竞赛数学专题班概率与期望习题

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Gildong 正在设计一个包含编号从 $1$ 到 $n$ 的 $n$ 个关卡组成的游戏。玩家从第一关开始并且需要按照关卡编号升序通过每一关。当玩家通过第 $n$ 关时获得胜利。

每一个关卡中至多有一个检查点，并且第一关一定存在一个检查点。在游戏开始的时候，只有第一关的检查点是被激活的，其他所有检查点都是未激活状态。当玩家到达一个拥有检查点的关卡时，该检查点会被激活。

对于每一个关卡，玩家可能会成功通过或者失败。如果玩家通过了第 $i$ 个关卡，他就可以移动到第 $i+1$ 个关卡。如果他们失败了，他们会回到最近激活的检查点处，并需要重新通过检查点以后的关卡。

例如，假设 $n=4$ 并且检查点位于第一个和第三个关卡。玩家从第一关开始，如果他失败，那么他就需要重新尝试第一关因为第一关的检查点是最近激活的检查点。如果他通过了第一关并且移动到第二关，但是他在第二关失败，那么他会重新回到第一关。如果他通过了第一关和第二关，那么他就会到达第三关并且第三关的检查点会被激活。现在无论他在第三关失败，还是通过第三关后在第四关失败，他都会被送回第三关。如果他通过了第三关和第四关，他就获得了胜利。

Gildong 计划将关卡设置为相同的难度。他想要你设计一个至多有 2000 关的方案，使得获胜所需要通过关卡的期望次数恰好为 $k$ 。

对于一个玩家而言，通过每一关的概率恰好为 $\frac{1}{2}$ 。

输入描述:

第一行包含一个整数 ，代表数据组数。

每组数据包含恰好一行。该行包含一个整数 ——获胜所需要通过关卡的期望次数如果玩家通过每个关卡的概率恰好为 。

输出描述:

对于每组数据，输出  如果无法构建一个满足条件的至多 2000 关的方案。

否则，输出两行。第一行应该包含一个整数 ，表示关卡的数量。第二行应该包含  个整数，第  个整数表示第  关是否有检查点。如果第  关没有检查点，第  个整数应该为 0 ，否则为 1。第一个整数应该始终为 1。

示例1

输入

复制

输出

复制