题号：NC217332
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
题目描述
比那瑞星人把你锁在了一个房间里圈养，用“比那瑞锁”将唯一的出口锁住，这个锁只有0，1两个按键，密码也只有0，1两个数字，一个密码用一次就会自动重置，难道这就是传说中的一次一密？你列出了每次他输入的每一个数字：
01101001100101101001011001101001...
突然醍醐灌顶，初始时，序列为空，其生成的规律是这样的：
- 如果
为空，那么
.
- 如果
你想知道这个密码锁第n次使用后,下一个密码是什么。
输入描述:
第一行是一个整数，表示测试数据组数。
接下来的T行，每行一个数字，表示含义见题目描述。
输出描述:
一共T行，每行一个0或者1.