### 问题描述 小然手中有一个长度为 $N$ 的二进制字符串 $S$，它是一个数 $X$ 的二进制表示。 他可以进行一次操作，具体如下： - 选择一个整数 $Y$，满足 $1 \leq Y \leq N$。 - 计算 $X_{new} = X \oplus \left\lfloor \frac{2^N}{2^Y} \right\rfloor$，其中 $\oplus$ 表示异或操作，$\left\lfloor \frac{2^N}{2^Y} \right\rfloor$ 表示 $2^N$ 除以 $2^Y$ 的结果向下取整。 - 将 $X$ 替换为 $X_{new}$。 小然的目标是通过一次操作，使得 $X$ 的值尽可能大。 请你帮助小然找出哪个 $Y$ 可以让 $X$ 的值最大。 ### 输入格式 输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例由两行组成： - 第一行包含一个整数 $N$，表示二进制字符串的长度。 - 第二行包含一个长度为 $N$ 的二进制字符串 $S$。 ### 输出格式 对于每个测试用例，输出一行一个整数 $Y$，表示可以使 $X$ 的值最大的 $Y$ 的值。 ### 样例输入 ```text 4 2 10 2 11 3 101 3 110 ``` ### 样例输出 ```text 1 2 1 2 ``` ### 说明 在第一组测试用例中，由于字符串 $S = 10$ 是数字 $2$ 的二进制表示，所以初始的 $X$ 值为 2。如果我们选择 $Y = 1$，那么 $X$ 将变为 $X \oplus \left\lfloor \frac{2}{2^1} \right\rfloor = 2 \oplus 1 = 3$。我们可以证明，这是在进行一次操作后我们可以得到的 $X$ 的最大值。 ### 评测数据范围 $1 \leq T \leq 10^3$。 $1 \leq |S| \leq 10^5$。 $S$ 中只包含 $0$ 或 $1$。 所有测试用例 $|S|$ 的总和不超过 $5 \times 10^5$。