思路

这个问题本质上是要求我们模拟题目中描述的二分搜索过程。我们并不知道秘密数字 $x$ 是什么，但我们知道每一次比较的结果。我们可以利用这些结果来逐步缩小搜索范围，就像“天才”那一方所做的一样。

1. 初始化范围：我们和“笨蛋”一样，从相同的初始范围开始。设置下界 $l=1$ 和上界 $r=2^{20}$。$2^{20}$ 的具体数值是 $1048576$。

2. 模拟猜测过程：我们得到了一个包含 $20$ 个字符的结果字符串。我们需要从第一个字符开始，遍历这个字符串，模拟每一轮的决策。

3. 更新边界：对于字符串中的每一个字符（假设是第 $i$ 次猜测的结果），我们执行以下操作：

题目内容

天才选择了一个秘密整数 $x$ ，其范围为 $[1,2^{20}]$ 。笨蛋按固定的二分策略进行 $20$ 次猜测。每次猜测流程如下：

• 维护当前可能范围 $[l,r]$(初始 $l=1,r=2^{20}$ ，均为闭区间)；

• 取中位数 $g=[\frac{l+r+1}{2}]$ 作为本轮猜测；

• 若 $g>x$ (猜大了)，天才返回字符 $1$ ，并将区间更新为 $[l,g-1]$ ；否则返回字符 $0$ ，并将区间更新为 $[g,r]$ ；

重复上述过程共 $20$ 轮。现在给出这 $20$ 次的返回结果(从第 $1$ 轮到第 $20$ 轮)，请你还原 $x$ 的值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数

$T(1≤ T ≤ 1000)$ 表示数据组数，每组测试数据描述如下

• 一行输入一个仅由 $0$ 与 $1$ 构成、长度恰为 $20$ 的字符串，依次对应 $20$ 次返回值。

输出描述

对于每组测试数据，单独输出一行一个整数，为被还原的 $x ($满足 $1≤x≤ 2^{20})$ 。

样例1

输入

3
00000000000000000000
11111111111111111111
10110000000000000000

输出

1048576
1
327680

说明

第一组：始终返回 $0$ ，区间不断向右收缩，最终为 $2^{20}=1048576$ ；

第二组：始终返回 $1$ ，区间不断向左收缩，最终为 $1$ 。