CF1936B Pinball

有一个长度为 $n$ 的一维网格，第 $i$ 个格子中包含一个字符 $s_i$，该字符要么是 ''。 当在某个格子上放置一个弹珠时，弹珠会按照以下规则移动： - 如果弹珠当前在第 $i$ 个格子且 $s_i$ 是 ''，则向右移动一个格子。 - 弹珠移动后，$s_i$ 的字符会反转（即如果 $s_i$ 原本是 ''，反之亦然）。 - 当弹珠离开网格（即从左边界或右边界离开）时，弹珠停止移动。 你需要回答 $n$ 个独立的询问。在第 $i$ 个询问中，弹珠会被放在第 $i$ 个格子上。注意，每次都在初始网格上放置弹珠。 对于每个询问，计算弹珠离开网格所需的秒数。可以证明，弹珠总能在有限步内离开网格。

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^5$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）。 第二行包含一个长度为 $n$ 的字符串 $s_1s_2\ldots s_n$，仅由字符 '' 组成。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，对于每个 $i$（$1 \le i \le n$），输出当弹珠初始放在第 $i$ 个格子时的答案。

在第一个测试用例中，$i=1$ 时弹珠的移动如下图所示。弹珠需要 $3$ 秒离开网格。  $i=2$ 时弹珠的移动如图所示。弹珠需要 $6$ 秒离开网格。  由 ChatGPT 4.1 翻译