gza 有一系列的字符串，第 个名为 。 S0=1; S1=10; S2=1001; S3=10010110; ⋯⋯

是 逐位取反后拼接在 后的串。你需要求 的第 个字符是什么。多测。 输入格式 第一行一个整数 ，表示数据组数。 接下来 行，一行一个整数，表示 ，含义见题目描述。 输出格式 一共 行，一行一个字符，表示答案。 输入样例 输出样例 数据描述 全部数据小于10^7