AT_scpc2026_div3_e.DETOX

$N$ students, numbered from $1$ to $N$, are seated in a circle in numerical order. Each student wears a name tag marked with either O or X. Each student can see the name tags of $N-1$ students, excluding their own. No three or more students sitting next to each other have name tags with the same letter, and all students are aware of this fact.

The game continues until every student has correctly guessed the letter on their own name tag. The rules of the game are as follows:

• In each round, all students who are certain of the letter on their name tag raise their hands at the same time.
• Once all students have confirmed which students raised their hands in this round, the next round begins.

During the game, no student may exchange name tags with others, remove their name tag, or change the letter on their name tag.

You are given $T$ test cases. For each test case, determine in which round each student will raise their hand for the first time.

$N$ 名学生，编号从 $1$ 到 $N$，按编号顺序围成一圈就座。每名学生佩戴一个标有字母 O 或 X 的姓名牌。每名学生都能看到其余 $N-1$ 名学生的姓名牌，但看不到自己的姓名牌。任意相邻的三名或以上学生，其姓名牌上的字母均不完全相同；所有学生均知晓这一事实。

游戏持续进行，直至每名学生都正确猜出自己姓名牌上的字母为止。游戏规则如下：

• 每一轮中，所有能确定自己姓名牌上字母的学生同时举手；
• 所有学生确认本回合哪些人举手后，进入下一轮。

游戏过程中，任何学生均不得与他人交换姓名牌、摘下自己的姓名牌，或更改自己姓名牌上的字母。

给定 $T$ 组测试数据。对每组测试数据，确定每名学生首次举手的轮次。

The input is given from Standard Input in the following format:

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format:

$N$
$S$

输入从标准输入中按以下格式给出：

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

每个测试用例按以下格式给出：

$N$
$S$

Output $N$ non-negative integers, separated by spaces, on a single line for each test case. The $i$th integer, $r_i$, indicates the $r_i$th round in which student $i$ first raises their hand. If there is a student who cannot raise their hand no matter how long the game continues, output -1 instead.

对每个测试用例，在一行中输出 $N$ 个非负整数，以空格分隔。其中第 $i$ 个整数 $r_i$ 表示学生 $i$ 首次举手所在的轮次（即第 $r_i$ 轮）。若存在某位学生无论游戏进行多长时间都无法举手，则对应位置输出 -1。

表示言語

/ /

Sample 1 Explanation:
In the first test case, four students are seated in a circle, each wearing a name tag labeled X, O, X, and O, respectively.

In the first round, Student $2$ observes that both Student $1$ and Student $3$ are wearing name tags labeled X. If Student $2$ were wearing a badge marked with X, then Students $2$, $3$, and $4$ would all be wearing badges marked with X, which contradicts the rule that three students sitting consecutively cannot all have badges marked with the same character.

Therefore, Student $2$ cannot be wearing a name tag marked with an X and can be certain that they are wearing a name tag marked with an O, so they raise their hand in the first round. The other students also raise their hands in the first round based on the same reasoning.

Constraints

• $1 \le T \le 100\,000$
• $3 \le N \le 100\,000$
• $S$ is a string of length $N$ consisting only of O and X.
  • The $i$th character of $S$ is the character written on the name tag of the $i$th student.
• None of the three students sitting consecutively are wearing name tags with the same characters written on them.
• The sum of $N$ over all test cases is at most $300\,000$.
• All input numbers are integers.

表示语言

/ /

样例 1 解释：
在第一个测试用例中，四名学生围成一圈就座，各自佩戴的姓名牌上分别标有 X、O、X 和 O。

在第一轮中，学生 $2$ 观察到学生 $1$ 和学生 $3$ 佩戴的姓名牌均标有 X。若学生 $2$ 佩戴的姓名牌也标有 X，则学生 $2$、$3$、$4$ 将全部佩戴标有 X 的姓名牌，这与“任意三名连续就座的学生不能全部佩戴相同字符的姓名牌”这一规则相矛盾。

因此，学生 $2$ 不可能佩戴标有 X 的姓名牌，从而可以确定自己佩戴的是标有 O 的姓名牌，于是在第一轮中举手。其余学生也基于相同的推理在第一轮中举手。

约束条件

• $1 \le T \le 100\,000$
• $3 \le N \le 100\,000$
• $S$ 是一个长度为 $N$ 的字符串，仅由字符 O 和 X 组成。
  • 字符串 $S$ 的第 $i$ 个字符即为第 $i$ 名学生所佩戴姓名牌上的字符。
• 任意三名连续就座的学生所佩戴的姓名牌上不全为相同字符。
• 所有测试用例的 $N$ 值之和不超过 $300\,000$。
• 所有输入数据均为整数。