当前没有测试数据。

斐波那契二进制序列

给定一个由斐波那契数构成的无限序列： 1010110101000101101010001… 序列的构成规则是：将斐波那契数的二进制表示拼接起来。即，序列为第1个斐波那契数的二进制表示紧接第2个斐波那契数的二进制表示……依次下去。

现在给定一个位置，求该位置上的字符（0或1）。

输入格式

• 第一行是一个正整数 N，表示询问的次数。
• 接下来 N 行，每行一个正整数，表示查询的位置。

输出格式

• 对于每个询问，输出该位置的字符（0或1）。

题解思路

1. 根据斐波那契数列，计算其二进制表示并拼接成字符串。

2. 找到查询的目标位置，输出对应的字符。

   输入:

   3 5 15 30

输出:

1 1 0