SP11844 BSPRIME - Binary Sequence of Prime Number

素数的二进制序列是通过将素数转换为二进制并去掉前导零得到的序列。例如： - 2 的二进制表示为 10 - 3 的二进制表示为 11 - 5 的二进制表示为 101 - 7 的二进制表示为 111 将所有素数的二进制表示按顺序连接，会生成一个无限长的二进制序列：10111011111011110110... 现在，你需要计算这个序列的前 **N** 位中，数字 '1' 出现了多少次。例如： - 如果 $N=3$，序列的前 3 位是 101，'1' 出现了 2 次。 - 如果 $N=10$，序列的前 10 位是 1011101111，'1' 出现了 8 次。

输入的第一行有一个整数 **T**，表示测试用例的数量。（$1 \le T \le 10^5$） 接下来 **T** 行，每行包含一个整数 **N**，表示需要考虑的二进制序列的前 **N** 位。（$0 \le N \le 10^6$）

对于每个测试用例，输出该二进制序列的前 **N** 位中数字 '1' 的出现次数。 **本翻译由 AI 自动生成**