SP693 LWAR - Lethal Warfare

一场重大的宇宙战即将结束。星际超级大国受到了攻击，但它们防御得相当不错。现在，它们准备发动最后的反击。然而，敌舰数量庞大，并且容易分散。根据太空战专家的建议，唯一可行的方法是针对排成一列的敌舰进行轰炸。 由于敌舰的总数是 2 的幂次，为了轰炸所有敌舰（编号从 0 到 $2^N - 1$），我们将使用一种称为 **BombStrat** 的策略，具体如下： 1. 从左到右轰炸前半部分，即 \[0 到 $2^{N-1} - 1$\]。 2. 对于剩下的后半部分，从右到左轰炸它的后半段，即按顺序轰炸编号为 $2^N - 1, 2^N - 2, \ldots, 2^{N-1} + 2^{N-2}$ 的敌舰。 3. 然后对剩下的敌舰 \[$2^{N-1}$ 到 $2^{N-1} + 2^{N-2} - 1$\] 继续使用 **BombStrat**。 例如，当 $N=3$ 时，也就是敌舰编号从 0 到 $2^3 - 1$ 时，轰炸的顺序如下： - 第一步：依次轰炸编号为 0, 1, 2, 3 的敌舰。 - 第二步：接着轰炸编号为 7, 6 的敌舰。 - 第三步：最后同样策略轰炸剩余的敌舰 \[4, 5\]。 因此，完整的轰炸顺序是 0 -> 1 -> 2 -> 3 -> 7 -> 6 -> 4 -> 5。为了简化星际超级大国的飞行员任务，他们希望知道每艘敌舰在何时被击中。你的任务是，给定 $N$ 和一艘敌舰的描述，输出该敌舰被轰炸的序列号（从 0 开始计数）。

- 第一行是整数 $T$，表示测试用例的数量，$T \leq 50$。 - 对于每个测试用例，包含一行二进制数，表示敌舰的编号。这个字符串的长度等于 $N$（如果必要会被补零）。$N \leq 30000$。

对于每个测试用例，输出炸弹的顺序号，表示为长度恰好为 $N$ 的二进制数字。

- $1 \leq T \leq 50$ - $1 \leq N \leq 30000$ **本翻译由 AI 自动生成**